<!DOCTYPE html>



  


<html class="theme-next gemini use-motion" lang="en">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>
<meta name="theme-color" content="#222">









<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css" />


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png?v=5.1.4">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png?v=5.1.4">


  <link rel="mask-icon" href="/images/logo.svg?v=5.1.4" color="#222">





  <meta name="keywords" content="Hexo, NexT" />










<meta property="og:type" content="website">
<meta property="og:title" content="LinRaise&#39;s Blog">
<meta property="og:url" content="http://yoursite.com/index.html">
<meta property="og:site_name" content="LinRaise&#39;s Blog">
<meta property="og:locale" content="en_US">
<meta property="article:author" content="LinRaise">
<meta name="twitter:card" content="summary">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Gemini',
    version: '5.1.4',
    sidebar: {"position":"right","display":"post","offset":12,"b2t":false,"scrollpercent":false,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: 'Author'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://yoursite.com/"/>





  <title>LinRaise's Blog</title>
  








<meta name="generator" content="Hexo 4.2.1"></head>

<body itemscope itemtype="http://schema.org/WebPage" lang="en">

  
  
    
  

  <div class="container sidebar-position-right 
  page-home">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/"  class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">LinRaise's Blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <p class="site-subtitle"></p>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-question-circle"></i> <br />
            
            Home
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-question-circle"></i> <br />
            
            About
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-question-circle"></i> <br />
            
            Tags
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-question-circle"></i> <br />
            
            Categories
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-question-circle"></i> <br />
            
            Archives
          </a>
        </li>
      

      
        <li class="menu-item menu-item-search">
          
            <a href="javascript:;" class="popup-trigger">
          
            
              <i class="menu-item-icon fa fa-search fa-fw"></i> <br />
            
            Search
          </a>
        </li>
      
    </ul>
  

  
    <div class="site-search">
      
  <div class="popup search-popup local-search-popup">
  <div class="local-search-header clearfix">
    <span class="search-icon">
      <i class="fa fa-search"></i>
    </span>
    <span class="popup-btn-close">
      <i class="fa fa-times-circle"></i>
    </span>
    <div class="local-search-input-wrapper">
      <input autocomplete="off"
             placeholder="Searching..." spellcheck="false"
             type="text" id="local-search-input">
    </div>
  </div>
  <div id="local-search-result"></div>
</div>



    </div>
  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            
  <section id="posts" class="posts-expand">
    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/08/02/%E6%95%B0%E7%BB%84%E4%B8%AD%E6%89%BE%E5%87%BA%E4%B8%A4%E4%B8%AA%E5%8F%AA%E5%87%BA%E7%8E%B0%E4%B8%80%E6%AC%A1%E7%9A%84%E6%95%B0%E5%AD%97/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="LinRaise">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="LinRaise's Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2020/08/02/%E6%95%B0%E7%BB%84%E4%B8%AD%E6%89%BE%E5%87%BA%E4%B8%A4%E4%B8%AA%E5%8F%AA%E5%87%BA%E7%8E%B0%E4%B8%80%E6%AC%A1%E7%9A%84%E6%95%B0%E5%AD%97/" itemprop="url">数组中找出两个只出现一次的数字</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">Posted on</span>
              
              <time title="Post created" itemprop="dateCreated datePublished" datetime="2020-08-02T15:00:38+00:00">
                2020-08-02
              </time>
            

            
              <span class="post-meta-divider">|</span>
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-check-o"></i>
              </span>
              
                <span class="post-meta-item-text">Post modified&#58;</span>
              
              <time title="Post modified" itemprop="dateModified" datetime="2020-08-02T15:00:38+00:00">
                2020-08-02
              </time>
            
          </span>

          
            <span class="post-category" >
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">In</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。</p>
<p>思路：题目要求时间复杂度是O(n)，空间复杂度是O(1)，这说明基于比较的办法求解无法完成，这题需要异或的性质，异或（同为0,异为1,相当于不进位加法）</p>
<p>因为其它数都出现两次，当扫描完一次之后，将所有的数做异或，那些相同的数都会变成0,结果是两个不同的数的异或。例如，9,4,4,2做异或，4,4异或为0,结果就相当于9异或2。</p>
<p>这里有两个数字不同，假设只有一个数字不同，那么，我们只需要扫描一遍，所有数做异或就可以得出结果。有两个数字怎么办呢？思路就是将这两个数划分到两个不同的组去。</p>
<p>划分依据是什么呢？</p>
<p>1，可以这么做，先将所有的数异或起来，假设结果为11001100,那么可以用最低的1位划分（即第2位，低到高，从0数起）[实质上可以用任何一个1划分，只是这是最方便的]，为什么1可以划分开两个不同的数呢？将两个数写成二进制的形式，那么异或结果显示出的1位（同时两个不同的数相异或必然有1,因为同则必为0），都是二者相应位不同的。（异为1,同为0）,因此用1划分则不同的两数必然被分到两个不同组</p>
<p>2，第二步，将两个子数组的数做异或就能得出结果，因为相同的数会得0.</p>
<p>3，小技巧，中途需要判断位是否为1,方法是：先将要判断的位通过右移移到最末位，然后与0000…..00001做位与，末位是1,则结果是1,若末位是0,结果是0</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/*一个整型数组里除了两个数字之外，其他的数字都出现了两次。</span></span><br><span class="line"><span class="comment">请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，</span></span><br><span class="line"><span class="comment">空间复杂度是O(1)*/</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">FindFirstbitis1</span><span class="params">(<span class="keyword">int</span> sum)</span><span class="comment">//找到第一个位是1（右往左）的索引号</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">int</span> index=<span class="number">0</span>;</span><br><span class="line">	<span class="keyword">while</span>((<span class="number">1</span> &amp; sum)==<span class="number">0</span>)<span class="comment">//和000..00001做与，若末位为0，即等于0,若末位为1,即为1</span></span><br><span class="line">	&#123;</span><br><span class="line">		sum=sum&gt;&gt;<span class="number">1</span>;</span><br><span class="line">		++index;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> index;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">judgeindexbitis1</span><span class="params">(<span class="keyword">int</span> num,<span class="keyword">int</span> index)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	num = num &gt;&gt; index;<span class="comment">//右移index位，使要判断的一位处于最末位</span></span><br><span class="line">	<span class="keyword">return</span>(<span class="number">1</span> &amp; num);<span class="comment">//和000..0001与，1则返回1,0则返回0</span></span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">xor</span><span class="params">(<span class="keyword">int</span>* A,<span class="keyword">int</span> len)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">int</span> sum=<span class="number">0</span>;<span class="comment">//两相异的数</span></span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;len;++i)</span><br><span class="line">	&#123;</span><br><span class="line">		sum =sum ^ A[i];</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">int</span> index=FindFirstbitis1(sum);</span><br><span class="line">	<span class="keyword">int</span> num1=<span class="number">0</span>,num2=<span class="number">0</span>;<span class="comment">//保存结果</span></span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;len;++i)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">if</span>(judgeindexbitis1(A[i],index))</span><br><span class="line">			num1 =num1 ^ A[i];</span><br><span class="line">		<span class="keyword">else</span> num2=num2 ^ A[i];</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="built_in">cout</span>&lt;&lt;num1&lt;&lt;<span class="string">" "</span>&lt;&lt;num2&lt;&lt;<span class="built_in">endl</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">int</span> A[]=&#123;<span class="number">9</span>,<span class="number">0</span>,<span class="number">0</span>,<span class="number">3</span>,<span class="number">3</span>,<span class="number">8</span>,<span class="number">8</span>,<span class="number">55</span>,<span class="number">55</span>,<span class="number">8888</span>,<span class="number">8888</span>,<span class="number">5</span>&#125;;</span><br><span class="line">	<span class="keyword">int</span> len=<span class="keyword">sizeof</span>(A)/<span class="keyword">sizeof</span>(A[<span class="number">0</span>]);</span><br><span class="line">	<span class="keyword">xor</span>(A,len);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/08/02/%E6%A0%B9%E6%8D%AE%E5%89%8D%E5%BA%8F%E9%81%8D%E5%8E%86%E5%92%8C%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86%EF%BC%8C%E9%87%8D%E6%9E%84%E5%87%BA%E4%BA%8C%E5%8F%89%E6%A0%91/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="LinRaise">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="LinRaise's Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2020/08/02/%E6%A0%B9%E6%8D%AE%E5%89%8D%E5%BA%8F%E9%81%8D%E5%8E%86%E5%92%8C%E4%B8%AD%E5%BA%8F%E9%81%8D%E5%8E%86%EF%BC%8C%E9%87%8D%E6%9E%84%E5%87%BA%E4%BA%8C%E5%8F%89%E6%A0%91/" itemprop="url">根据前序遍历和中序遍历，重构出二叉树</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">Posted on</span>
              
              <time title="Post created" itemprop="dateCreated datePublished" datetime="2020-08-02T15:00:38+00:00">
                2020-08-02
              </time>
            

            
              <span class="post-meta-divider">|</span>
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-check-o"></i>
              </span>
              
                <span class="post-meta-item-text">Post modified&#58;</span>
              
              <time title="Post modified" itemprop="dateModified" datetime="2020-08-02T15:00:38+00:00">
                2020-08-02
              </time>
            
          </span>

          
            <span class="post-category" >
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">In</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>根据前序遍历和中序遍历，重构出二叉树</p>
<p>题目：这道题目是一道面试题，先序遍历和中序遍历以数组的形式给出，要求我们根据这两个条件重构出二叉树。</p>
<p>下图是一棵二叉树</p>
<figure class="highlight graph"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">//              6</span><br><span class="line">//           /     \</span><br><span class="line">//          5       7  </span><br><span class="line">//         / \       \</span><br><span class="line">//        2   4       8</span><br></pre></td></tr></table></figure>

<p>先序遍历：6,5,2,4,7,8</p>
<p>中序遍历：2,5,4,6,7,8</p>
<p>思路：二叉树先序遍历的定义：1,先输出根结点2,再输出左子树3,再输出右子树，因此先序遍历时，根结点总会出现在数组开头，中序遍历时，根结点可以将二叉树分为左右子树。</p>
<p>因此，重构二叉树的步骤可以用自顶向下的方法：</p>
<p>1,先在先序序列中找到根结点,</p>
<p>2,在中序序列中找到根结点位置,(可以将二叉树分为左子树和右子树)</p>
<p>3.用同样的办法构造左子树</p>
<p>4.用同样的办法构造右子树。</p>
<p>例如：</p>
<p>1.找到根结点6,因此左子树是2,5,4和右子树是7,8</p>
<p>2.找到左边根结点5,可将子二叉树分为2和4,因此左边确定。</p>
<p>3,找到右边根结点7,因此可确定右子树8。</p>
<p>根据四步走可以写出如出代码：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="function">node* <span class="title">Build_Tree</span><span class="params">(<span class="keyword">int</span>* prec,<span class="keyword">int</span>* inorder,<span class="keyword">int</span> len)</span></span></span><br><span class="line"><span class="function"></span>&#123;	<span class="comment">//步骤1:新建根结点</span></span><br><span class="line">	node* root=<span class="keyword">new</span> node(prec[<span class="number">0</span>]);</span><br><span class="line">	<span class="comment">//步骤2:在中序遍历中找到根结点索引，分割左右子树</span></span><br><span class="line">	<span class="keyword">int</span> SubTreeLen=<span class="number">0</span>;</span><br><span class="line">	<span class="keyword">while</span>(SubTreeLen &lt; len &amp;&amp; inorder[SubTreeLen] != prec[<span class="number">0</span>])</span><br><span class="line">		++SubTreeLen;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">if</span>(SubTreeLen &gt; <span class="number">0</span>)</span><br><span class="line">	&#123;	<span class="comment">//步骤2:重建左子树，并且将根结点root的left指向左子树</span></span><br><span class="line">		root-&gt;left=Build_Tree(prec+<span class="number">1</span>,inorder,SubTreeLen);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span>(len-SubTreeLen<span class="number">-1</span> &gt; <span class="number">0</span>)</span><br><span class="line">	&#123;	<span class="comment">//步骤2:重建右子树，并且将根结点root的left指向右子树</span></span><br><span class="line">		root-&gt;right=Build_Tree(prec+<span class="number">1</span>+SubTreeLen,inorder+<span class="number">1</span>+SubTreeLen,len-SubTreeLen<span class="number">-1</span>);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> root;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>接下来的步骤就是进行程序测试，利用边界值等去测试程序的健壮性。</p>
<p>可以利用下面的二叉树去测试：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F; 普通二叉树</span><br><span class="line">&#x2F;&#x2F;              1</span><br><span class="line">&#x2F;&#x2F;           &#x2F;     \</span><br><span class="line">&#x2F;&#x2F;          2       3  </span><br><span class="line">&#x2F;&#x2F;         &#x2F;       &#x2F; \</span><br><span class="line">&#x2F;&#x2F;        4       5   6</span><br><span class="line">&#x2F;&#x2F;         \         &#x2F;</span><br><span class="line">&#x2F;&#x2F;          7       8</span><br><span class="line">	int preorder[length] &#x3D; &#123;1, 2, 4, 7, 3, 5, 6, 8&#125;;</span><br><span class="line">	int inorder[length] &#x3D; &#123;4, 7, 2, 1, 5, 3, 8, 6&#125;;</span><br><span class="line"> </span><br><span class="line">&#x2F;&#x2F; 所有结点都没有右子结点</span><br><span class="line">&#x2F;&#x2F;            1</span><br><span class="line">&#x2F;&#x2F;           &#x2F; </span><br><span class="line">&#x2F;&#x2F;          2   </span><br><span class="line">&#x2F;&#x2F;         &#x2F; </span><br><span class="line">&#x2F;&#x2F;        3 </span><br><span class="line">&#x2F;&#x2F;       &#x2F;</span><br><span class="line">&#x2F;&#x2F;      4</span><br><span class="line">&#x2F;&#x2F;     &#x2F;</span><br><span class="line">&#x2F;&#x2F;    5</span><br><span class="line"> </span><br><span class="line">	int preorder[length] &#x3D; &#123;1, 2, 3, 4, 5&#125;;</span><br><span class="line">	int inorder[length] &#x3D; &#123;5, 4, 3, 2, 1&#125;;</span><br><span class="line"> </span><br><span class="line">&#x2F;&#x2F; 所有结点都没有左子结点</span><br><span class="line">&#x2F;&#x2F;            1</span><br><span class="line">&#x2F;&#x2F;             \ </span><br><span class="line">&#x2F;&#x2F;              2   </span><br><span class="line">&#x2F;&#x2F;               \ </span><br><span class="line">&#x2F;&#x2F;                3 </span><br><span class="line">&#x2F;&#x2F;                 \</span><br><span class="line">&#x2F;&#x2F;                  4</span><br><span class="line">&#x2F;&#x2F;                   \</span><br><span class="line">&#x2F;&#x2F;                    5</span><br><span class="line">	int preorder[length] &#x3D; &#123;1, 2, 3, 4, 5&#125;;</span><br><span class="line">	int inorder[length] &#x3D; &#123;1, 2, 3, 4, 5&#125;;</span><br><span class="line"> </span><br><span class="line">&#x2F;&#x2F; 树中只有一个结点</span><br><span class="line">    int preorder[length] &#x3D; &#123;1&#125;;</span><br><span class="line">    int inorder[length] &#x3D; &#123;1&#125;;</span><br><span class="line">&#x2F;&#x2F; 完全二叉树</span><br><span class="line">&#x2F;&#x2F;              1</span><br><span class="line">&#x2F;&#x2F;           &#x2F;     \</span><br><span class="line">&#x2F;&#x2F;          2       3  </span><br><span class="line">&#x2F;&#x2F;         &#x2F; \     &#x2F; \</span><br><span class="line">&#x2F;&#x2F;        4   5   6   7</span><br><span class="line">    int preorder[length] &#x3D; &#123;1, 2, 4, 5, 3, 6, 7&#125;;</span><br><span class="line">    int inorder[length] &#x3D; &#123;4, 2, 5, 1, 6, 3, 7&#125;;</span><br><span class="line"> </span><br><span class="line">&#x2F;&#x2F; 输入空指针</span><br><span class="line"> </span><br><span class="line">&#x2F;&#x2F; 输入的两个序列不匹配</span><br><span class="line"> </span><br><span class="line">    int preorder[length] &#x3D; &#123;1, 2, 4, 5, 3, 6, 7&#125;;</span><br><span class="line">    int inorder[length] &#x3D; &#123;4, 2, 8, 1, 6, 3, 7&#125;;</span><br></pre></td></tr></table></figure>

<p>上述测试例子引自于：《剑指Offer——名企面试官精讲典型编程题》</p>
<p>经过测试，当输入空指针和两个序列不匹配时，原始的程序无办法处理，可以针对性处理如下：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;exception&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="built_in">std</span>::<span class="built_in">cout</span>;</span><br><span class="line"><span class="keyword">using</span> <span class="built_in">std</span>::<span class="built_in">endl</span>;</span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">node</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">	<span class="keyword">int</span> value;</span><br><span class="line">	node* left;</span><br><span class="line">	node* right;</span><br><span class="line">	node(<span class="keyword">int</span> v):value(v),left(<span class="literal">NULL</span>),right(<span class="literal">NULL</span>)&#123;&#125;</span><br><span class="line">&#125;;</span><br><span class="line"> </span><br><span class="line"><span class="function">node* <span class="title">Build_Tree</span><span class="params">(<span class="keyword">int</span>* prec,<span class="keyword">int</span>* inorder,<span class="keyword">int</span> len)</span></span></span><br><span class="line"><span class="function"></span>&#123;	</span><br><span class="line">	<span class="keyword">if</span>(!prec || !inorder || len &lt;=<span class="number">0</span> )</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="built_in">cout</span>&lt;&lt;<span class="string">"Empty Input!"</span>&lt;&lt;<span class="built_in">endl</span>;</span><br><span class="line">		<span class="built_in">exit</span>(<span class="number">1</span>);<span class="comment">//暴力关机</span></span><br><span class="line">	&#125;</span><br><span class="line">	<span class="comment">//步骤1:新建根结点</span></span><br><span class="line">	node* root=<span class="keyword">new</span> node(prec[<span class="number">0</span>]);</span><br><span class="line">	<span class="comment">//步骤2:在中序遍历中找到根结点索引，分割左右子树</span></span><br><span class="line">	<span class="keyword">int</span> SubTreeLen=<span class="number">0</span>;</span><br><span class="line">	<span class="keyword">while</span>(SubTreeLen &lt; len &amp;&amp; inorder[SubTreeLen] != prec[<span class="number">0</span>])</span><br><span class="line">		++SubTreeLen;</span><br><span class="line">	<span class="keyword">if</span>(SubTreeLen == len)<span class="comment">//越界了，说明两个数组无法构造出二叉树</span></span><br><span class="line">	&#123;</span><br><span class="line">		<span class="built_in">cout</span>&lt;&lt;<span class="string">"Wrong Input!"</span>&lt;&lt;<span class="built_in">endl</span>;</span><br><span class="line">		<span class="built_in">exit</span>(<span class="number">1</span>);<span class="comment">//暴力关机</span></span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span>(SubTreeLen &gt; <span class="number">0</span>)</span><br><span class="line">	&#123;	<span class="comment">//步骤2:重建左子树，并且将根结点root的left指向左子树</span></span><br><span class="line">		root-&gt;left=Build_Tree(prec+<span class="number">1</span>,inorder,SubTreeLen);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span>(len-SubTreeLen<span class="number">-1</span> &gt; <span class="number">0</span>)</span><br><span class="line">	&#123;	<span class="comment">//步骤2:重建右子树，并且将根结点root的left指向右子树</span></span><br><span class="line">		root-&gt;right=Build_Tree(prec+<span class="number">1</span>+SubTreeLen,inorder+<span class="number">1</span>+SubTreeLen,len-SubTreeLen<span class="number">-1</span>);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> root;</span><br><span class="line">&#125;</span><br><span class="line"> </span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">prec_tree_walk</span><span class="params">(node* z)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(!z)</span><br><span class="line">		<span class="keyword">return</span> ;</span><br><span class="line">	<span class="built_in">cout</span>&lt;&lt;z-&gt;value&lt;&lt;<span class="string">' '</span>;</span><br><span class="line">	prec_tree_walk(z-&gt;left);</span><br><span class="line">	prec_tree_walk(z-&gt;right);</span><br><span class="line">&#125;</span><br><span class="line"> </span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">inorder_tree_walk</span><span class="params">(node* z)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(!z)</span><br><span class="line">		<span class="keyword">return</span> ;</span><br><span class="line">	inorder_tree_walk(z-&gt;left);</span><br><span class="line">	<span class="built_in">cout</span>&lt;&lt;z-&gt;value&lt;&lt;<span class="string">' '</span>;</span><br><span class="line">	inorder_tree_walk(z-&gt;right);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">int</span> prec[] = &#123;<span class="number">1</span>, <span class="number">2</span>, <span class="number">4</span>, <span class="number">7</span>, <span class="number">3</span>, <span class="number">5</span>, <span class="number">6</span>, <span class="number">8</span>&#125;;</span><br><span class="line">	<span class="keyword">int</span> Inorder[] = &#123;<span class="number">4</span>, <span class="number">7</span>, <span class="number">2</span>, <span class="number">1</span>, <span class="number">5</span>, <span class="number">3</span>, <span class="number">8</span>, <span class="number">6</span>&#125;;</span><br><span class="line"> </span><br><span class="line">	<span class="keyword">int</span> len=<span class="keyword">sizeof</span>(prec)/<span class="keyword">sizeof</span>(prec[<span class="number">0</span>]);</span><br><span class="line">	node* root=Build_Tree(prec,Inorder,len);</span><br><span class="line">	prec_tree_walk(root);</span><br><span class="line">	<span class="built_in">cout</span>&lt;&lt;<span class="built_in">endl</span>;</span><br><span class="line">	inorder_tree_walk(root);</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/08/02/Hexo%20Guide/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="LinRaise">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="LinRaise's Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2020/08/02/Hexo%20Guide/" itemprop="url">Hexo Guide</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">Posted on</span>
              
              <time title="Post created" itemprop="dateCreated datePublished" datetime="2020-08-02T15:00:38+00:00">
                2020-08-02
              </time>
            

            
              <span class="post-meta-divider">|</span>
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-check-o"></i>
              </span>
              
                <span class="post-meta-item-text">Post modified&#58;</span>
              
              <time title="Post modified" itemprop="dateModified" datetime="2020-08-02T15:00:38+00:00">
                2020-08-02
              </time>
            
          </span>

          
            <span class="post-category" >
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">In</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/hexo/" itemprop="url" rel="index">
                    <span itemprop="name">hexo</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>Welcome to <a href="https://hexo.io/" target="_blank" rel="noopener">Hexo</a>! This is your very first post. Check <a href="https://hexo.io/docs/" target="_blank" rel="noopener">documentation</a> for more info. If you get any problems when using Hexo, you can find the answer in <a href="https://hexo.io/docs/troubleshooting.html" target="_blank" rel="noopener">troubleshooting</a> or you can ask me on <a href="https://github.com/hexojs/hexo/issues" target="_blank" rel="noopener">GitHub</a>.</p>
<h2 id="Quick-Start"><a href="#Quick-Start" class="headerlink" title="Quick Start"></a>Quick Start</h2><h3 id="Create-a-new-post"><a href="#Create-a-new-post" class="headerlink" title="Create a new post"></a>Create a new post</h3><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">$ hexo new <span class="string">"My New Post"</span></span><br></pre></td></tr></table></figure>

<p>More info: <a href="https://hexo.io/docs/writing.html" target="_blank" rel="noopener">Writing</a></p>
<h3 id="Run-server"><a href="#Run-server" class="headerlink" title="Run server"></a>Run server</h3><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">$ hexo server</span><br></pre></td></tr></table></figure>

<p>More info: <a href="https://hexo.io/docs/server.html" target="_blank" rel="noopener">Server</a></p>
<h3 id="Generate-static-files"><a href="#Generate-static-files" class="headerlink" title="Generate static files"></a>Generate static files</h3><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">$ hexo generate</span><br></pre></td></tr></table></figure>

<p>More info: <a href="https://hexo.io/docs/generating.html" target="_blank" rel="noopener">Generating</a></p>
<h3 id="Deploy-to-remote-sites"><a href="#Deploy-to-remote-sites" class="headerlink" title="Deploy to remote sites"></a>Deploy to remote sites</h3><figure class="highlight bash"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">$ hexo deploy</span><br></pre></td></tr></table></figure>

<p>More info: <a href="https://hexo.io/docs/one-command-deployment.html" target="_blank" rel="noopener">Deployment</a></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/08/02/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F-%E6%B1%82%E9%80%86%E5%BA%8F%E6%95%B0%E7%AE%97%E6%B3%95/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="LinRaise">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="LinRaise's Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2020/08/02/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F-%E6%B1%82%E9%80%86%E5%BA%8F%E6%95%B0%E7%AE%97%E6%B3%95/" itemprop="url">归并排序-求逆序数算法</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">Posted on</span>
              
              <time title="Post created" itemprop="dateCreated datePublished" datetime="2020-08-02T15:00:38+00:00">
                2020-08-02
              </time>
            

            
              <span class="post-meta-divider">|</span>
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-check-o"></i>
              </span>
              
                <span class="post-meta-item-text">Post modified&#58;</span>
              
              <time title="Post modified" itemprop="dateModified" datetime="2020-08-02T15:00:38+00:00">
                2020-08-02
              </time>
            
          </span>

          
            <span class="post-category" >
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">In</span>
              
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/algorithm/" itemprop="url" rel="index">
                    <span itemprop="name">algorithm</span>
                  </a>
                </span>

                
                
              
            </span>
          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>算法：归并排序是分治法(分而治之)的一种典型应用，应用递归的思想，自顶向下思考：先假定MergeSort()可以将一个乱序的数组排好序，因此就可以开始”分”(将一个数组平均分成两部分），再”治”(分别对前后部分调用MergeSort()使它们有序)，最后再写一个合并子函数Merge()，它可以将两个有序的数组合并，Merge()实现起来比较容易．只需要管理两个指针，分别指向两个子数组的开头，开辟新内存保存中间结果，遍历完两个数组就可以完成，时间是Θ(n).</p>
<p>假定n个元素的数组调用MergeSort()需要时间T(n).因此，T(n)=2T(n/2)+Θ(n)．由主定理可知：T(n)=Θ(nlogn).归并排序算法的时间复杂度是Θ(nlogn)，空间复杂度是Θ(n).</p>
<p>由归并排序扩展可以求逆序数．</p>
<p>　　逆序数的定义：如果 i &lt; j 且A[i] &gt; A[j].则A[i]和A[j]即为逆序数对．逆序数对的个数就叫逆序数．因此求逆序数可以通过管理两个指针，两次扫描数组，蛮力法求出，显然时间复杂度是Θ(n^2).那么有更快的办法吗？答案是肯定的，利用归并排序法，稍做改进即可．在Merge()中，合并两个已经有序的数组A,B.因为A.B有序,所以,A,B各自的逆序数是0,所以AB的逆序数等于A,B之间的逆序数.</p>
<p>举个例子: A=1,4,6,7,9 B=2,3,5,10,13,21.在Merge中发现当前i号元素4比2大,那么4的逆序数需要+1,又因6,7,9都排在4后面,那么6,7,9的逆序数也应该+1,所以总体的逆序数应该加上last-i+1.(如果i号元素比B[j]小（比如4比5小）,无法确定逆序数的变化,不作任何修改).</p>
<p><img src="/2020/08/02/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F-%E6%B1%82%E9%80%86%E5%BA%8F%E6%95%B0%E7%AE%97%E6%B3%95/20130924234354406.png" alt></p>
<p>代码:</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">int</span> count=<span class="number">0</span>;<span class="comment">//新增</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Merge</span><span class="params">(<span class="keyword">int</span>* A,<span class="keyword">int</span> left,<span class="keyword">int</span> mid,<span class="keyword">int</span> right,<span class="keyword">int</span>* C)</span></span></span><br><span class="line"><span class="function"></span>&#123;	<span class="comment">//Merge可以将两个有序的数组排好序,时间复杂度:o(n)</span></span><br><span class="line">	<span class="keyword">int</span> i=left;</span><br><span class="line">	<span class="keyword">int</span> j=mid+<span class="number">1</span>;</span><br><span class="line">	<span class="keyword">int</span> k=left;</span><br><span class="line">	<span class="keyword">while</span>(i &lt;= mid &amp;&amp; j &lt;= right)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">if</span>(A[i] &lt;= A[j])</span><br><span class="line">			C[k++]=A[i++];</span><br><span class="line">		<span class="keyword">else</span></span><br><span class="line">		&#123;</span><br><span class="line">			C[k++]=A[j++];</span><br><span class="line">			count += mid-i+<span class="number">1</span>;<span class="comment">//新增</span></span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">while</span>(i &lt;= mid)</span><br><span class="line">		C[k++]=A[i++];</span><br><span class="line">	<span class="keyword">while</span>(j &lt;= right)</span><br><span class="line">		C[k++]=A[j++];</span><br><span class="line">	<span class="comment">//C[]已经有序，将C[]中数据复制回原数组A[]</span></span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=left;i &lt;= right;++i)</span><br><span class="line">		A[i]=C[i];</span><br><span class="line">&#125;	</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">MergeSort</span><span class="params">(<span class="keyword">int</span>* A,<span class="keyword">int</span> left,<span class="keyword">int</span> right,<span class="keyword">int</span>* C)</span><span class="comment">//假定MergeSort能将一个乱序数组A排好序．</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">if</span>(left &lt; right)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">int</span> mid=(left+right)/<span class="number">2</span>;</span><br><span class="line">		MergeSort(A,left,mid,C);<span class="comment">//排好一个数组1</span></span><br><span class="line">		MergeSort(A,mid+<span class="number">1</span>,right,C);<span class="comment">//排好一个数组2</span></span><br><span class="line">		Merge(A,left,mid,right,C); <span class="comment">//合并两个有序的数组</span></span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"> </span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">int</span> A[]=&#123;<span class="number">2</span>,<span class="number">1</span>,<span class="number">3</span>,<span class="number">6</span>,<span class="number">4</span>,<span class="number">0</span>,<span class="number">11</span>,<span class="number">3</span>,<span class="number">5</span>&#125;;</span><br><span class="line">	<span class="keyword">int</span> len=<span class="keyword">sizeof</span>(A)/<span class="keyword">sizeof</span>(A[<span class="number">0</span>]);</span><br><span class="line">	<span class="keyword">int</span> *C=<span class="keyword">new</span> <span class="keyword">int</span>[len];</span><br><span class="line">	MergeSort(A,<span class="number">0</span>,len<span class="number">-1</span>,C);</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;len;++i)</span><br><span class="line">		<span class="built_in">cout</span>&lt;&lt;A[i]&lt;&lt;<span class="string">' '</span>;</span><br><span class="line">	<span class="built_in">cout</span>&lt;&lt;<span class="built_in">endl</span>;</span><br><span class="line">	<span class="built_in">cout</span>&lt;&lt;count&lt;&lt;<span class="built_in">endl</span>;</span><br><span class="line">	<span class="keyword">delete</span>[] C;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/07/24/Hexo%E6%90%AD%E9%85%8DGithub%E4%B8%8ETravis-Ci%E6%90%AD%E5%BB%BA%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="LinRaise">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="LinRaise's Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2020/07/24/Hexo%E6%90%AD%E9%85%8DGithub%E4%B8%8ETravis-Ci%E6%90%AD%E5%BB%BA%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/" itemprop="url">Hexo搭配Github与Travis-Ci搭建个人博客</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">Posted on</span>
              
              <time title="Post created" itemprop="dateCreated datePublished" datetime="2020-07-24T14:45:25+00:00">
                2020-07-24
              </time>
            

            
              <span class="post-meta-divider">|</span>
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-check-o"></i>
              </span>
              
                <span class="post-meta-item-text">Post modified&#58;</span>
              
              <time title="Post modified" itemprop="dateModified" datetime="2020-07-24T14:45:25+00:00">
                2020-07-24
              </time>
            
          </span>

          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p><strong>已经有现成的第三方博客了，为什么还要自己折腾？</strong></p>
<p>中文社区有很多博客托管的网站，例如CSDN, 博客园，简书等等。与此同时，还有一些笔记类的工具可供选择，例如印像笔记，OneNote等等。但是，今天这些都不是我们讨论的重点，我们今天的重点是讨论一下如何利用Hexo, Github和Travis-CI来搭建并且自动化布署我们的个人博客，那么这样做的好处是什么呢？我想到了以下几点：</p>
<ol>
<li>避免各大博客门户网站的广告植入。</li>
<li>更加的极客风格，完全以源代码的方式管控我们自己的博客，迁移和改动都十分便利。</li>
<li>由于Hexo的博客风格样式十分的清新简洁，因此，十分适合我的品味。</li>
<li>Travis-CI自动集成自动发布的特点，因此，管控文章的方式十分的优雅。</li>
</ol>
<p><strong>Hexo+Github+Travis-Ci的工作原理是什么呢？</strong></p>
<p>Hexo是一个Node.js的项目，主要是将Markdown语法的文章渲染并生成静态的HTML页面，</p>
<p>再通过Github Pages将静态的HTML显示出来可以达到博客的效果，</p>
<p>而Travis-Ci的作用主要是根据Github的提交实时触发Hexo的解释并生成静态页面，无需人工参与发布操作。</p>
<p><strong>软件依赖：</strong></p>
<ol>
<li>Node.js</li>
<li>Git</li>
<li>TortoiseGit (可选)</li>
</ol>
<p>首先需要先申请一下Github帐号,</p>
<p>访问<code>https://github.com/</code>⟶<code>Sign up</code></p>
<img src="/2020/07/24/Hexo%E6%90%AD%E9%85%8DGithub%E4%B8%8ETravis-Ci%E6%90%AD%E5%BB%BA%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/image-20200727110730633.png" alt="image-20200727110730633" style="zoom:70%;">

<p>新建一个<code>公有</code>项目，<code>{account-name}</code>.github.io，在本文中是<code>hexoblog1.github.io</code>,这个仓库主要是托管<code>公有</code>的静态HTML页面。</p>
<img src="/2020/07/24/Hexo%E6%90%AD%E9%85%8DGithub%E4%B8%8ETravis-Ci%E6%90%AD%E5%BB%BA%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/image-20200727114001930.png" alt="image-20200727114001930" style="zoom: 70%;">

<p>新建一个<code>私有</code>项目<code>hexoblog1</code>,这个仓库主要是托管<code>私有</code>的Markdown源文件，因为无须对外公布源文件。</p>
<img src="/2020/07/24/Hexo%E6%90%AD%E9%85%8DGithub%E4%B8%8ETravis-Ci%E6%90%AD%E5%BB%BA%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/image-20200727155149660.png" alt="image-20200727155149660" style="zoom:70%;">

<p>还有一件很重要的事情，需要为github仓库生成token，Travis-ci需要根据github生成的token来访问github的代码仓库。</p>
<p>访问<a href="https://github.com/settings/tokens⟶`Generate" target="_blank" rel="noopener">https://github.com/settings/tokens⟶`Generate</a> new token`，起名GH_TOKEN，需要在生成的时候复制出来，因为这个TOKEN只会在生成的时候显示。</p>
<p><img src="/2020/07/24/Hexo%E6%90%AD%E9%85%8DGithub%E4%B8%8ETravis-Ci%E6%90%AD%E5%BB%BA%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/image-20200727161447684.png" alt="image-20200727161447684"></p>
<p>拥有了TOKEN之后，使用Github帐号登录<a href="https://travis-ci.com/⟶`Sign" target="_blank" rel="noopener">https://travis-ci.com/⟶`Sign</a> In<code>⟶</code>SIGN IN WITH GITHUB<code>⟶ 选中托管源文件的</code>hexoblog1<code>仓库⟶</code>More Options<code></code>Settings`⟶添加环境变量GH_TOKEN，（VALUE就是上一步GITHUB生成的TOKEN值）用于访问github仓库</p>
<blockquote>
<p>注意：不要勾选DISPLAY VALUE IN BUILD LOG, 避免在Travis-CI的Build日志中导致token泄露<br>注意：这里不能访问<a href="https://travis-ci.org,因为这个网站目前并不能支持私有仓库。" target="_blank" rel="noopener">https://travis-ci.org,因为这个网站目前并不能支持私有仓库。</a></p>
</blockquote>
<p><img src="/2020/07/24/Hexo%E6%90%AD%E9%85%8DGithub%E4%B8%8ETravis-Ci%E6%90%AD%E5%BB%BA%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/image-20200727161059567.png" alt="image-20200727161059567"></p>
<p>至此，Travis-CI与Github仓库的连接已经通过GH_TOKEN建立起来了，下面着重讨论Hexo的配置，执行以下命令生成基本的Hexo 博客框架；</p>
<figure class="highlight js"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">npm install hexo-cli -g <span class="comment">/**install scaffolding**/</span></span><br><span class="line">hexo init hexoblog1		<span class="comment">/**initial the blog by clone from remote github repository**/</span></span><br><span class="line">cd hexoblog1			<span class="comment">/**go to the blog folder**/</span></span><br><span class="line">npm install				<span class="comment">/**install the project**/</span></span><br><span class="line">hexo server				<span class="comment">/**start the server**/</span></span><br></pre></td></tr></table></figure>

<figure class="highlight yaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="string">(node:9296)</span> <span class="attr">ExperimentalWarning:</span> <span class="string">The</span> <span class="string">fs.promises</span> <span class="string">API</span> <span class="string">is</span> <span class="string">experimental</span></span><br><span class="line"><span class="string">INFO</span>  <span class="string">Start</span> <span class="string">processing</span></span><br><span class="line"><span class="string">INFO</span>  <span class="string">Hexo</span> <span class="string">is</span> <span class="string">running</span> <span class="string">at</span> <span class="string">http://localhost:4000</span> <span class="string">.</span> <span class="string">Press</span> <span class="string">Ctrl+C</span> <span class="string">to</span> <span class="string">stop.</span></span><br></pre></td></tr></table></figure>

<p>访问<a href="http://localhost:4000可以看到默认的hexo为我们生成的页面。">http://localhost:4000可以看到默认的hexo为我们生成的页面。</a></p>
<p>参考这篇</p>
<p>添加Travis-Ci必需的<code>.travis.yml</code>配置文件，<code>yaml-1</code></p>
<figure class="highlight yml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="attr">sudo:</span> <span class="literal">false</span></span><br><span class="line"><span class="attr">language:</span> <span class="string">node_js</span></span><br><span class="line"><span class="attr">node_js:</span></span><br><span class="line">  <span class="bullet">-</span> <span class="number">10</span> <span class="comment"># use nodejs v10 LTS</span></span><br><span class="line"><span class="attr">cache:</span> <span class="string">npm</span></span><br><span class="line"><span class="attr">branches:</span></span><br><span class="line">  <span class="attr">only:</span></span><br><span class="line">    <span class="bullet">-</span> <span class="string">master</span> <span class="comment"># build hexo branch only</span></span><br><span class="line"><span class="attr">script:</span></span><br><span class="line">  <span class="bullet">-</span> <span class="string">hexo</span> <span class="string">generate</span> <span class="comment"># generate static files</span></span><br><span class="line"><span class="attr">deploy:</span></span><br><span class="line">  <span class="attr">provider:</span> <span class="string">pages</span></span><br><span class="line">  <span class="attr">skip-cleanup:</span> <span class="literal">true</span>                    <span class="comment"># Make sure you have skip_cleanup set to true, otherwise Travis CI will delete all the files created during the build, which will probably delete what you are trying to upload.</span></span><br><span class="line">  <span class="attr">local-dir:</span> <span class="string">public</span>                     <span class="comment"># Directory to push to GitHub Pages, defaults to current directory. Can be specified as an absolute path or a relative path from the current directory.</span></span><br><span class="line">  <span class="attr">target-branch:</span> <span class="string">master</span>                 <span class="comment"># Branch to (force, see: keep_history) push local_dir contents to, defaults to gh-pages.</span></span><br><span class="line">  <span class="attr">repo:</span> <span class="string">hexoblog1/hexoblog1.github.io</span>   <span class="comment"># Repo slug, defaults to current repo. <span class="doctag">Note:</span> The slug consists of username and repo name and is formatted like user/repo-name.</span></span><br><span class="line">  <span class="attr">github-token:</span> <span class="string">$GH_TOKEN</span>               <span class="comment"># Set in the settings page of your repository, as a secure variable</span></span><br><span class="line">  <span class="attr">keep-history:</span> <span class="literal">false</span>                   <span class="comment"># Optional, create incremental commit instead of doing push force, defaults to false.</span></span><br><span class="line">  <span class="attr">on:</span></span><br><span class="line">    <span class="attr">branch:</span> <span class="string">master</span>                      <span class="comment"># source code branch</span></span><br></pre></td></tr></table></figure>

<p>以上是以Travis-CI默认提供的provider来实现推送，我们也可以通过自定义脚本来实现相同的目的，如下：<code>yaml-2</code></p>
<figure class="highlight yaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="attr">sudo:</span> <span class="literal">false</span></span><br><span class="line"><span class="attr">language:</span> <span class="string">node_js</span></span><br><span class="line"><span class="attr">node_js:</span></span><br><span class="line">  <span class="bullet">-</span> <span class="number">10</span> <span class="comment"># use nodejs v10 LTS</span></span><br><span class="line"><span class="attr">cache:</span> <span class="string">npm</span></span><br><span class="line"><span class="attr">branches:</span></span><br><span class="line">  <span class="attr">only:</span></span><br><span class="line">    <span class="bullet">-</span> <span class="string">master</span> <span class="comment"># build hexo branch only</span></span><br><span class="line"><span class="attr">script:</span></span><br><span class="line">  <span class="bullet">-</span> <span class="string">hexo</span> <span class="string">generate</span> <span class="comment"># generate static files</span></span><br><span class="line"><span class="attr">after_script:</span></span><br><span class="line">  <span class="bullet">-</span> <span class="string">cd</span> <span class="string">./public</span></span><br><span class="line">  <span class="bullet">-</span> <span class="string">git</span> <span class="string">init</span></span><br><span class="line">  <span class="bullet">-</span> <span class="string">git</span> <span class="string">config</span> <span class="string">user.name</span> <span class="string">"Deployment Bot"</span></span><br><span class="line">  <span class="bullet">-</span> <span class="string">git</span> <span class="string">config</span> <span class="string">user.email</span> <span class="string">"deploy@travis-ci.org"</span></span><br><span class="line">  <span class="bullet">-</span> <span class="string">git</span> <span class="string">add</span> <span class="string">.</span></span><br><span class="line">  <span class="bullet">-</span> <span class="string">git</span> <span class="string">commit</span> <span class="string">-m</span> <span class="string">"deploy $&#123;GH_REPO&#125;"</span></span><br><span class="line">  <span class="bullet">-</span> <span class="string">git</span> <span class="string">push</span> <span class="string">--force</span> <span class="string">--quiet</span> <span class="string">"https://$&#123;GH_TOKEN&#125;@$&#123;GH_REPO&#125;"</span> <span class="string">master:master</span></span><br><span class="line"><span class="attr">branches:</span></span><br><span class="line">  <span class="attr">only:</span></span><br><span class="line">    <span class="bullet">-</span> <span class="string">master</span></span><br><span class="line"><span class="attr">env:</span></span><br><span class="line"> <span class="attr">global:</span></span><br><span class="line">   <span class="bullet">-</span> <span class="attr">GH_REPO:</span> <span class="string">github.com/hexoblog1/hexoblog1.github.io.git</span></span><br></pre></td></tr></table></figure>

<p>至此，一个完整的Hexo+Github+Travis-CI的链路就已经建好了，但是博客显示的效果还不是很好，接下来我们需要做一些优化；</p>
<ol>
<li>把博客主题换成Next; </li>
</ol>
<p>   安装next主题只需要clone最新的next项目到themes目录下即可，</p>
   <figure class="highlight shell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">$</span><span class="bash"> <span class="built_in">cd</span> your-hexo-site</span></span><br><span class="line"><span class="meta">$</span><span class="bash"> git <span class="built_in">clone</span> https://github.com/iissnan/hexo-theme-next themes/next</span></span><br></pre></td></tr></table></figure>

<p>   启用next主题，需要修改根目录的配置文件<code>_config.yml</code>，同时定制一些个性化内容，如下</p>
   <figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">theme: next</span><br><span class="line">title: Hexoblog1</span><br><span class="line">author: hexoblog1</span><br><span class="line">post_asset_folder: true</span><br><span class="line">use_date_for_updated: true</span><br></pre></td></tr></table></figure>

<p>   同时我们还想添加博客搜索查询功能，在根目录下执行以下命令安装<code>hexo-generator-searchdb</code></p>
   <figure class="highlight shell"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">npm install hexo-generator-searchdb --save</span><br></pre></td></tr></table></figure>

<p>   添加以下内容到根目录的配置文件<code>_config.yml</code></p>
   <figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">search:</span><br><span class="line">    path: search.xml</span><br><span class="line">    field: post</span><br><span class="line">    format: html</span><br><span class="line">    limit: 10000</span><br></pre></td></tr></table></figure>

<p>   在<code>themes/next/_config.yml</code>中启用本地搜索</p>
   <figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">local_search:</span><br><span class="line">  enable: true</span><br></pre></td></tr></table></figure>

<p>   选择 Scheme需要切换到<code>/themes/next_config.yml</code>,修改为以下配置，我选择的是Gemini</p>
   <figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"># ---------------------------------------------------------------</span><br><span class="line"># Scheme Settings</span><br><span class="line"># ---------------------------------------------------------------</span><br><span class="line"></span><br><span class="line"># Schemes</span><br><span class="line">#scheme: Muse</span><br><span class="line">#scheme: Mist</span><br><span class="line">#scheme: Pisces</span><br><span class="line">scheme: Gemini</span><br></pre></td></tr></table></figure>

<p>   为博客添加<code>tags</code>，<code>about</code>，<code>categories</code>，<code>archives</code>等栏目，首先修改<code>/themes/next/_config.yml</code>的Menu节点，如下（删除原条目<code>||</code>及右边的内容），我们还可以启用缓存功能，使得博客加载速度提升。</p>
   <figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">home: &#x2F;</span><br><span class="line">about: &#x2F;about&#x2F;</span><br><span class="line">tags: &#x2F;tags&#x2F;</span><br><span class="line">categories: &#x2F;categories&#x2F;</span><br><span class="line">archives: &#x2F;archives&#x2F;</span><br><span class="line"></span><br><span class="line">cache:</span><br><span class="line">  enable:true #speed up the loading</span><br></pre></td></tr></table></figure>
<p>   同时在根目录下依次执行下列命令生成对应的md模板，<br>   <figure class="highlight shell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">$</span><span class="bash"> hexo new page about</span></span><br><span class="line"><span class="meta">$</span><span class="bash"> hexo new page tags</span></span><br><span class="line"><span class="meta">$</span><span class="bash"> hexo new page categories</span></span><br><span class="line"><span class="meta">$</span><span class="bash"> hexo new page archives</span></span><br></pre></td></tr></table></figure></p>
<p>   添加图片插件<code>hexo-easy-images</code>，该插件会自动将图片URL自动转储至项目的相对路径并且更新markdown的链接，</p>
<p>   注意：这个插件依赖<code>sharp</code>插件（10MB），因此安装过程比较慢，</p>
   <figure class="highlight shell"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">npm i hexo-easy-images -s</span><br></pre></td></tr></table></figure>

<p>   凑巧最近<code>github pages</code>出故障无法正常访问，因此，我们可以考虑使用国内的<code>gitee pages</code>来托管我们的静态博客，</p>
<p>   准备工作：</p>
<ol>
<li><p>创建一个<code>Gitee</code>帐号并且创建一个名为<code>hexoblog1</code>的空项目，不需要<code>.gitee.io</code>后缀（与<code>github</code>操作类似，这里不再讲述，开通<code>pages</code>功能需要绑定手机）</p>
</li>
<li><p>创建一个<code>Gitee</code>的<code>personal access token</code>，先保存token文本，下面有用（与<code>github</code>操作类似，这里不再讲述）参考见下：</p>
<p>[Gitee access token]: <a href="https://gitee.com/profile/personal_access_tokens3" target="_blank" rel="noopener">https://gitee.com/profile/personal_access_tokens3</a>.</p>
</li>
<li><p>在Travis-CI.com上添加一个<code>GITEE_TOKEN</code>的环境变量，将第2步的token文本填入Value字段，这样GITEE与Travis-CI的联系就可以建立了</p>
</li>
<li><p>修改<code>.travis.yml</code>配置如下，添加GITEE的推送地址即可，这样一来当更新提交时，<code>Travis-CI</code>会同时发布到<code>GITHUB</code>和<code>Gitee</code></p>
<p><strong>注意</strong>：GITEE PAGE的自动更新是收费的，因此每次发布博客完成之后，都需要登录<code>Gitee</code>手动来刷新页面，十分不方便，好在<code>Gitee</code>提供了第三方的API来支持自动更新。</p>
</li>
</ol>
<pre><code>[更新Pages语法]: https://gitee.com/api/v5/swagger#/postV5ReposOwnerRepoPagesBuilds
[授权Token语法]: http://git.mydoc.io/?t=180695
<figure class="highlight yaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="string">用户名，密码方式：</span></span><br><span class="line"><span class="string">git</span> <span class="string">clone</span> <span class="string">https://gitee.com/zxzllyj/sample-project.git</span></span><br><span class="line"><span class="string">根据提示输入用户名密码</span></span><br><span class="line">      </span><br><span class="line"><span class="string">username</span> <span class="string">+</span> <span class="string">accessToken</span> <span class="string">方式：</span></span><br><span class="line"><span class="string">git</span> <span class="string">clone</span> <span class="string">https://zxzllyj:fb63d3ae801d73d7364cd7b2cacxxxd2a@gitee.com/zxzllyj/sample-project.git</span></span><br><span class="line">      </span><br><span class="line"><span class="string">oauth2</span> <span class="string">+</span> <span class="string">accessToken</span> <span class="string">方式：</span></span><br><span class="line"><span class="string">git</span> <span class="string">clone</span> <span class="string">https://oauth2:fb63d3ae801d73d7364cd7b2cacxxxd2a@gitee.com/zxzllyj/sample-project.git</span></span><br></pre></td></tr></table></figure>

因此，最终的`yaml`如下：

<figure class="highlight yaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line">   <span class="attr">sudo:</span> <span class="literal">false</span></span><br><span class="line">   <span class="attr">language:</span> <span class="string">node_js</span></span><br><span class="line">   <span class="attr">node_js:</span></span><br><span class="line">     <span class="bullet">-</span> <span class="number">10</span> <span class="comment"># use nodejs v10 LTS</span></span><br><span class="line">   <span class="attr">cache:</span> <span class="string">npm</span></span><br><span class="line">   <span class="attr">branches:</span></span><br><span class="line">     <span class="attr">only:</span></span><br><span class="line">       <span class="bullet">-</span> <span class="string">master</span> <span class="comment"># build hexo branch only</span></span><br><span class="line">   <span class="attr">script:</span></span><br><span class="line">     <span class="bullet">-</span> <span class="string">hexo</span> <span class="string">generate</span> <span class="comment"># generate static files</span></span><br><span class="line"><span class="attr">after_script:</span></span><br><span class="line">     <span class="bullet">-</span> <span class="string">cd</span> <span class="string">./public</span></span><br><span class="line">     <span class="bullet">-</span> <span class="string">git</span> <span class="string">init</span></span><br><span class="line">     <span class="bullet">-</span> <span class="string">git</span> <span class="string">config</span> <span class="string">user.name</span> <span class="string">"Deployment Bot"</span></span><br><span class="line">     <span class="bullet">-</span> <span class="string">git</span> <span class="string">config</span> <span class="string">user.email</span> <span class="string">"deploy@travis-ci.org"</span></span><br><span class="line">     <span class="bullet">-</span> <span class="string">git</span> <span class="string">add</span> <span class="string">.</span></span><br><span class="line">     <span class="bullet">-</span> <span class="string">git</span> <span class="string">commit</span> <span class="string">-m</span> <span class="string">"deploy $&#123;GH_REPO&#125;"</span></span><br><span class="line">     <span class="bullet">-</span> <span class="string">git</span> <span class="string">config</span> <span class="string">--global</span> <span class="string">--unset</span> <span class="string">http.proxy</span></span><br><span class="line">     <span class="bullet">-</span> <span class="string">git</span> <span class="string">config</span> <span class="string">--global</span> <span class="string">--unset</span> <span class="string">https.proxy</span></span><br><span class="line">     <span class="bullet">-</span> <span class="string">git</span> <span class="string">push</span> <span class="string">--force</span> <span class="string">--quiet</span> <span class="string">"https://$&#123;GH_TOKEN&#125;@$&#123;GH_REPO&#125;"</span> <span class="string">master:master</span></span><br><span class="line">     <span class="bullet">-</span> <span class="string">git</span> <span class="string">push</span> <span class="string">--force</span> <span class="string">--quiet</span> <span class="string">"https://oauth2:$&#123;GITEE_TOKEN&#125;@$&#123;GITEE_REPO&#125;"</span> <span class="string">master:master</span></span><br><span class="line">     <span class="bullet">-</span> <span class="string">curl</span> <span class="string">-X</span> <span class="string">POST</span> <span class="string">https://oauth2:$&#123;GITEE_TOKEN&#125;@gitee.com/api/v5/repos/hexoblog1/hexoblog1/pages/builds</span></span><br><span class="line">   </span><br><span class="line">   <span class="attr">branches:</span></span><br><span class="line">     <span class="attr">only:</span></span><br><span class="line">       <span class="bullet">-</span> <span class="string">master</span></span><br><span class="line">   <span class="attr">env:</span></span><br><span class="line">    <span class="attr">global:</span></span><br><span class="line">      <span class="bullet">-</span> <span class="attr">GH_REPO:</span> <span class="string">github.com/hexoblog1/hexoblog1.github.io.git</span></span><br><span class="line">      <span class="bullet">-</span> <span class="attr">GITEE_REPO:</span> <span class="string">gitee.com/hexoblog1/hexoblog1.git</span></span><br></pre></td></tr></table></figure></code></pre><p>   <strong>FAQ</strong></p>
<ol>
<li><p>能否将博客源文件和生成的页面都托管在Gitee ? </p>
<p>由于目当Travis-CI不支持与Gitee集成，如果需要使用Travis-CI的CICD功能，必须利用Github中转仓库</p>
</li>
</ol>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/07/20/%E7%BC%96%E7%A8%8B%E4%B9%8B%E7%BE%8E%E5%B0%86%E5%B8%85%E4%B8%8D%E7%85%A7%E9%9D%A2/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="LinRaise">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="LinRaise's Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2020/07/20/%E7%BC%96%E7%A8%8B%E4%B9%8B%E7%BE%8E%E5%B0%86%E5%B8%85%E4%B8%8D%E7%85%A7%E9%9D%A2/" itemprop="url">编程之美将帅不照面</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">Posted on</span>
              
              <time title="Post created" itemprop="dateCreated datePublished" datetime="2020-07-20T16:46:56+00:00">
                2020-07-20
              </time>
            

            
              <span class="post-meta-divider">|</span>
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-check-o"></i>
              </span>
              
                <span class="post-meta-item-text">Post modified&#58;</span>
              
              <time title="Post modified" itemprop="dateModified" datetime="2020-07-20T16:46:56+00:00">
                2020-07-20
              </time>
            
          </span>

          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>编程之美上的一道题：要求将帅不能照面，找到有多少种方式摆放“将”和“帅”，而且只能使用一个变量。</p>
<p>思考：如果蛮力法解决，只需要罗列出所有的可能性，然后排除掉那些不满足条件的情况就是结果了。但是，这里只能用一个变量保存结果，所以，需要一点技巧，先说一下《编程之美》是的解法2,因为解法2是最精妙的，个人认为，提供了一种新型的思考方式。先给出将帅在棋局的分布，有一个感观的认识再继续下面的操作：</p>
<p><img src="/2020/07/20/%E7%BC%96%E7%A8%8B%E4%B9%8B%E7%BE%8E%E5%B0%86%E5%B8%85%E4%B8%8D%E7%85%A7%E9%9D%A2/SouthEast" alt="img"></p>
<p>解法二：我们可以这么做，下面的二维特殊数k{1,2,3,4,5,….9},其中k=1,2,3,4,…..9.表示A中的k和B中的1,2,…9搭配成一对，这样子的话就可以搭配出9*9=81种可能性.理论上，我们只需要遍历完这81种情况就可以找到结果。A格子和B格子的棋子只有在同一列才会产生冲突。那么重点就是如何找到列数。</p>
<p>先列举出所以的可能性组合：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">１&#123;1,1&#125;&#123;1,2&#125;&#123;1,3&#125;&#123;1,4&#125;&#123;1,5&#125;&#123;1,6&#125;&#123;1,7&#125;&#123;1,8&#125;&#123;1,9&#125;</span><br><span class="line">２&#123;2,1&#125;&#123;2,2&#125;&#123;2,3&#125;&#123;2,4&#125;&#123;2,5&#125;&#123;2,6&#125;&#123;2,7&#125;&#123;2,8&#125;&#123;2,9&#125;</span><br><span class="line">３&#123;3,1&#125;&#123;3,2&#125;&#123;3,3&#125;&#123;3,4&#125;&#123;3,5&#125;&#123;3,6&#125;&#123;3,7&#125;&#123;3,8&#125;&#123;3,9&#125;</span><br><span class="line">４&#123;4,1&#125;&#123;4,2&#125;&#123;4,3&#125;&#123;4,4&#125;&#123;4,5&#125;&#123;4,6&#125;&#123;4,7&#125;&#123;4,8&#125;&#123;4,9&#125;</span><br><span class="line">５&#123;5,1&#125;&#123;5,2&#125;&#123;5,3&#125;&#123;5,4&#125;&#123;5,5&#125;&#123;5,6&#125;&#123;5,7&#125;&#123;5,8&#125;&#123;5,9&#125;</span><br><span class="line">６&#123;6,1&#125;&#123;6,2&#125;&#123;6,3&#125;&#123;6,4&#125;&#123;6,5&#125;&#123;6,6&#125;&#123;6,7&#125;&#123;6,8&#125;&#123;6,9&#125;</span><br><span class="line">７&#123;7,1&#125;&#123;7,2&#125;&#123;7,3&#125;&#123;7,4&#125;&#123;7,5&#125;&#123;7,6&#125;&#123;7,7&#125;&#123;7,8&#125;&#123;7,9&#125;</span><br><span class="line">８&#123;8,1&#125;&#123;8,2&#125;&#123;8,3&#125;&#123;8,4&#125;&#123;8,5&#125;&#123;8,6&#125;&#123;8,7&#125;&#123;8,8&#125;&#123;8,9&#125;</span><br><span class="line">９&#123;9,1&#125;&#123;9,2&#125;&#123;9,3&#125;&#123;9,4&#125;&#123;9,5&#125;&#123;9,6&#125;&#123;9,7&#125;&#123;9,8&#125;&#123;9,9&#125;</span><br></pre></td></tr></table></figure>

<p>第1行就是A中第1格和B中的九格对应的情况，其它类比如是</p>
<p>像<code>for(i=1;i&lt;=81;++i)</code>中的<code>i</code>,</p>
<p>如果我们想确定它是A中的第几格，怎么办？可以对i除以9，就知道它是第几行，即A中第几格，如果还想知道它在A中第几列，继续对它模3即可。</p>
<p>现在开始考虑B中的情况，如何知道当前i是B中的第几格？这个问题可以转化成如何知道它是上面二维数组中第几列，只需要对i模上9即可，那么如何知道它是B中的第几列呢？继续对它模上3即可。</p>
<p>小结拓展：</p>
<p>我们知道A[i][j]实质上表示的是A数组中(i*cols+j)号元素，那么，如果我们知道元素是第k号元素了，要如何确定它的行号和列号呢？<code>row=k/cols,col=k%cols</code>.再把这个基本思路套到上面应该能够找到一点灵感了。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;stdio.h&gt;</span><br><span class="line">int main()</span><br><span class="line">&#123;</span><br><span class="line">	int i&#x3D;81;</span><br><span class="line">	while(i--)</span><br><span class="line">	&#123;</span><br><span class="line">		if( i&#x2F;9%3 &#x3D;&#x3D; i%9%3)&#x2F;&#x2F;i&#x2F;9求的是行号(A中号码)，i%9求的是列号(B中号码)</span><br><span class="line">			continue;</span><br><span class="line">		printf(&quot;%d %d\n&quot;,i&#x2F;9+1,i%9+1);&#x2F;&#x2F;输出A,B中的号码</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<p>总结：<br>可以将A中的9个格子{1,2,3,4,5,6,7,8,9}当成行号，将B中的9个格子{1,2,3,4,5,6,7,8,9}当成列号，那么就可以组成一个A[i][j]二维数组，只不过题目要求我们只能使用一个变量，否则我们只需要保存两个变量i,j，遍历完整个数组就可以了。但是，我们也可以用一维数组的方式存储二维数组的下标，假定一维数组的下标是k,则i=k/cols,j=k%cols.</p>
<p>这让我想到这篇博文的35和36行。<a href="http://blog.csdn.net/linraise/article/details/12571025" target="_blank" rel="noopener">http://blog.csdn.net/linraise/article/details/12571025</a></p>
<p>剩下的就可以完全按照二维数组的形式解决这个问题了。</p>
<p>解法三：用一个结构体保存两个变量，实质上和直接使用二维下标的思路一样。这里不再多说。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line">int main()</span><br><span class="line">&#123;</span><br><span class="line">	struct </span><br><span class="line">	&#123;</span><br><span class="line">		unsigned char a:4;</span><br><span class="line">		unsigned char b:4;</span><br><span class="line">	&#125; i;</span><br><span class="line">	for(i.a&#x3D;1;i.a&lt;&#x3D;9;++i.a)</span><br><span class="line">	&#123;</span><br><span class="line">		for(i.b&#x3D;1;i.b&lt;&#x3D;9;++i.b)</span><br><span class="line">		&#123;</span><br><span class="line">			if( i.a % 3 !&#x3D; i.b % 3)</span><br><span class="line">				printf(&quot;A &#x3D; %d, B &#x3D; %d\n&quot;,i.a,i.b);</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>




          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/07/20/%E7%B4%A0%E6%95%B0%E7%AD%9B%E9%80%89%E6%B3%95/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="LinRaise">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="LinRaise's Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2020/07/20/%E7%B4%A0%E6%95%B0%E7%AD%9B%E9%80%89%E6%B3%95/" itemprop="url">素数筛选法</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">Posted on</span>
              
              <time title="Post created" itemprop="dateCreated datePublished" datetime="2020-07-20T16:33:02+00:00">
                2020-07-20
              </time>
            

            
              <span class="post-meta-divider">|</span>
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-check-o"></i>
              </span>
              
                <span class="post-meta-item-text">Post modified&#58;</span>
              
              <time title="Post modified" itemprop="dateModified" datetime="2020-07-20T16:33:02+00:00">
                2020-07-20
              </time>
            
          </span>

          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>素数筛选法</p>
<p>素数筛选法的目的就是筛选出在某一区间[m,n)内的所有素数，常见的办法有如下几种。</p>
<p><strong>１.朴素的筛选法</strong><br>朴素的筛选法思路很简单，先写一个判断是否是素数的函数isPrime()，然后从2到n分别调用isPrime()函数来检查。检查是否是质数的算法是核心，使用从2到n的开根的数作为除数（为什么是开根数呢？因为如果当前筛选到p,则说明1<em>p,2</em>p…..(p-1)<em>p已经在筛选1,2,3……p-1的时候被处理过了，现在我们只需要接着处理p</em>p即可，即要求p<em>p &lt;=n）。复杂度大概是O(n</em>log(n)).虽然复杂度看起来比较和谐，但是显然直觉告诉我们调用函数次数过多。 </p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line">bool isPrime(int n)</span><br><span class="line">&#123;</span><br><span class="line">	&#x2F;&#x2F;if we process p turn,then ,2*p,3*p,4*p,....(p-1)*p was processed</span><br><span class="line">	&#x2F;&#x2F;so we begin with p*p &lt; n;</span><br><span class="line"></span><br><span class="line">	int i,sqr &#x3D; sqrt((double)n);</span><br><span class="line">	for(i&#x3D;2; i&lt;&#x3D;sqr; ++i)</span><br><span class="line">	&#123;</span><br><span class="line">		if ( (n%i) &#x3D;&#x3D; 0 )</span><br><span class="line">			return false;</span><br><span class="line">	&#125;</span><br><span class="line">	return true;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>接下来如果需要找到[m,n)的素数，只需要在[m,n)上调用<code>isPrime()</code>函数n-m次即可。</p>
<p><strong>2.比朴素法更高效的筛选法</strong><br>我们知道要求某一区间内的素数，只需要将这一区间内的合数去除，即筛除即可，这种办法利用的就是这种思想。</p>
<p>例如：2,3,4,5,6,7,8,9,10,11,12,13,14,15…….</p>
<p>第一遍筛掉2的倍数:剩下2,3,5,7,9,11,13,15…..</p>
<p>第二遍筛掉3的倍数:剩下2,3,5,7,11,13,….</p>
<p>第三遍筛掉5的倍数:(为什么是5而不是4,因为4已经被2的倍数筛掉了，再筛已经无意义)</p>
<p>第四遍筛掉7的倍数:(为什么是7而不是6,同理因为6已经被之前的2,3筛掉了再筛也没有意义了)</p>
<p>下面用程序去模拟这个过程：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;iostream&gt;</span><br><span class="line">#include&lt;string&gt;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">const int N &#x3D; 30;</span><br><span class="line">int Prime[5000]; &#x2F;&#x2F;保存素数</span><br><span class="line">bool isPrime[5000];&#x2F;&#x2F;标记该位是否是素数</span><br><span class="line">int len;</span><br><span class="line"></span><br><span class="line">&#x2F;&#x2F;fin [2,N] &#39;s prime</span><br><span class="line">void SetPrime()</span><br><span class="line">&#123;</span><br><span class="line">	int i,j;</span><br><span class="line">	len &#x3D; 0;</span><br><span class="line">	memset(isPrime,true,sizeof(isPrime));</span><br><span class="line">	for(i&#x3D;2; i&lt;&#x3D;N; ++i)</span><br><span class="line">	&#123;</span><br><span class="line">		if(isPrime[i])</span><br><span class="line">		&#123;</span><br><span class="line">			Prime[len++] &#x3D; i;</span><br><span class="line">			for(j&#x3D;i+i; j&lt;&#x3D;N; j +&#x3D; i)</span><br><span class="line">				isPrime[j] &#x3D; false;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line">int main()</span><br><span class="line">&#123;</span><br><span class="line">	SetPrime();</span><br><span class="line">	int i;</span><br><span class="line">	for(i&#x3D;0; i&lt;len; ++i)</span><br><span class="line">		cout &lt;&lt; Prime[i] &lt;&lt;&#39; &#39;;</span><br><span class="line">	cout &lt;&lt; endl;</span><br><span class="line">	return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<p><strong>3.用动态规划进行素数筛选</strong></p>
<p>这种办法较之上面的办法在效率上没有改进，几乎效率相同，但是思路很新颖，而且可以省下上面的isPrime[]数组的</p>
<p>不必要开销。这种办法用到一个知识。即如果我们已经知道线性表的前边k个数中一共有m个素数(2,3,5,7…)，假定对于第k+1个元素，如果Array[k+1]不能被前m个素数整除，说明Array[k+1]是素数，新增之，如果Array[k+1]能被前m个素数中的某一个素数整除，则说明Array[k+1]不是素数，可以排除之，继续往后迭代，直至到达区间的末尾。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;Dynamic Programming find primes</span><br><span class="line">&#x2F;&#x2F;first step : find Status Prime[0] &#x3D; 2,</span><br><span class="line">&#x2F;&#x2F;second step: find the Transfer formula,</span><br><span class="line">&#x2F;&#x2F;when the number A[i] can % prime[0...i] &#x3D;&#x3D; 0,</span><br><span class="line">&#x2F;&#x2F;it&#39;s not a prime,else it is a prime.</span><br><span class="line">int prime[50000];</span><br><span class="line">int pLen;</span><br><span class="line">void SetPrime()&#x2F;&#x2F;dp set prime</span><br><span class="line">&#123;</span><br><span class="line">	int i,j;</span><br><span class="line">	pLen &#x3D; 1;</span><br><span class="line">	bool isPrime;</span><br><span class="line">	prime[0] &#x3D; 2;</span><br><span class="line">	for (i&#x3D;3; i&lt;50000; i +&#x3D; 2)</span><br><span class="line">	&#123;</span><br><span class="line">		isPrime &#x3D; true; &#x2F;&#x2F;assume it&#39;s a prime</span><br><span class="line">		for(j&#x3D;0; j&lt;pLen; ++j)</span><br><span class="line">		&#123;</span><br><span class="line">			if ( (i%prime[j]) &#x3D;&#x3D; 0 )</span><br><span class="line">			&#123;</span><br><span class="line">				isPrime &#x3D; false; &#x2F;&#x2F;if i mod prime[j] &#x3D;&#x3D;0,than it&#39;s not a prime</span><br><span class="line">				break;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		if ( isPrime )</span><br><span class="line">			prime[pLen++] &#x3D; i;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>4.工程方法筛选素数<br>如果我们需要经常用到素数表，为何要每用一次就调用一次函数呢？直接将素数表打印到文件中，到用时再直接读取不就可以了吗？</p>
<p>下面是[2,5000]内的素数表： </p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br></pre></td><td class="code"><pre><span class="line">2 3 5 7 11 13 17 19 23 29 31 37 41 43 47</span><br><span class="line">53 59 61 67 71 73 79 83 89 97 101 103 107 109 113</span><br><span class="line">127 131 137 139 149 151 157 163 167 173 179 181 191 193 197</span><br><span class="line">199 211 223 227 229 233 239 241 251 257 263 269 271 277 281</span><br><span class="line">283 293 307 311 313 317 331 337 347 349 353 359 367 373 379</span><br><span class="line">383 389 397 401 409 419 421 431 433 439 443 449 457 461 463</span><br><span class="line">467 479 487 491 499 503 509 521 523 541 547 557 563 569 571</span><br><span class="line">577 587 593 599 601 607 613 617 619 631 641 643 647 653 659</span><br><span class="line">661 673 677 683 691 701 709 719 727 733 739 743 751 757 761</span><br><span class="line">769 773 787 797 809 811 821 823 827 829 839 853 857 859 863</span><br><span class="line">877 881 883 887 907 911 919 929 937 941 947 953 967 971 977</span><br><span class="line">983 991 997 1009 1013 1019 1021 1031 1033 1039 1049 1051 1061 1063 1069</span><br><span class="line">1087 1091 1093 1097 1103 1109 1117 1123 1129 1151 1153 1163 1171 1181 1187</span><br><span class="line">1193 1201 1213 1217 1223 1229 1231 1237 1249 1259 1277 1279 1283 1289 1291</span><br><span class="line">1297 1301 1303 1307 1319 1321 1327 1361 1367 1373 1381 1399 1409 1423 1427</span><br><span class="line">1429 1433 1439 1447 1451 1453 1459 1471 1481 1483 1487 1489 1493 1499 1511</span><br><span class="line">1523 1531 1543 1549 1553 1559 1567 1571 1579 1583 1597 1601 1607 1609 1613</span><br><span class="line">1619 1621 1627 1637 1657 1663 1667 1669 1693 1697 1699 1709 1721 1723 1733</span><br><span class="line">1741 1747 1753 1759 1777 1783 1787 1789 1801 1811 1823 1831 1847 1861 1867</span><br><span class="line">1871 1873 1877 1879 1889 1901 1907 1913 1931 1933 1949 1951 1973 1979 1987</span><br><span class="line">1993 1997 1999 2003 2011 2017 2027 2029 2039 2053 2063 2069 2081 2083 2087</span><br><span class="line">2089 2099 2111 2113 2129 2131 2137 2141 2143 2153 2161 2179 2203 2207 2213</span><br><span class="line">2221 2237 2239 2243 2251 2267 2269 2273 2281 2287 2293 2297 2309 2311 2333</span><br><span class="line">2339 2341 2347 2351 2357 2371 2377 2381 2383 2389 2393 2399 2411 2417 2423</span><br><span class="line">2437 2441 2447 2459 2467 2473 2477 2503 2521 2531 2539 2543 2549 2551 2557</span><br><span class="line">2579 2591 2593 2609 2617 2621 2633 2647 2657 2659 2663 2671 2677 2683 2687</span><br><span class="line">2689 2693 2699 2707 2711 2713 2719 2729 2731 2741 2749 2753 2767 2777 2789</span><br><span class="line">2791 2797 2801 2803 2819 2833 2837 2843 2851 2857 2861 2879 2887 2897 2903</span><br><span class="line">2909 2917 2927 2939 2953 2957 2963 2969 2971 2999 3001 3011 3019 3023 3037</span><br><span class="line">3041 3049 3061 3067 3079 3083 3089 3109 3119 3121 3137 3163 3167 3169 3181</span><br><span class="line">3187 3191 3203 3209 3217 3221 3229 3251 3253 3257 3259 3271 3299 3301 3307</span><br><span class="line">3313 3319 3323 3329 3331 3343 3347 3359 3361 3371 3373 3389 3391 3407 3413</span><br><span class="line">3433 3449 3457 3461 3463 3467 3469 3491 3499 3511 3517 3527 3529 3533 3539</span><br><span class="line">3541 3547 3557 3559 3571 3581 3583 3593 3607 3613 3617 3623 3631 3637 3643</span><br><span class="line">3659 3671 3673 3677 3691 3697 3701 3709 3719 3727 3733 3739 3761 3767 3769</span><br><span class="line">3779 3793 3797 3803 3821 3823 3833 3847 3851 3853 3863 3877 3881 3889 3907</span><br><span class="line">3911 3917 3919 3923 3929 3931 3943 3947 3967 3989 4001 4003 4007 4013 4019</span><br><span class="line">4021 4027 4049 4051 4057 4073 4079 4091 4093 4099 4111 4127 4129 4133 4139</span><br><span class="line">4153 4157 4159 4177 4201 4211 4217 4219 4229 4231 4241 4243 4253 4259 4261</span><br><span class="line">4271 4273 4283 4289 4297 4327 4337 4339 4349 4357 4363 4373 4391 4397 4409</span><br><span class="line">4421 4423 4441 4447 4451 4457 4463 4481 4483 4493 4507 4513 4517 4519 4523</span><br><span class="line">4547 4549 4561 4567 4583 4591 4597 4603 4621 4637 4639 4643 4649 4651 4657</span><br><span class="line">4663 4673 4679 4691 4703 4721 4723 4729 4733 4751 4759 4783 4787 4789 4793</span><br><span class="line">4799 4801 4813 4817 4831 4861 4871 4877 4889 4903 4909 4919 4931 4933 4937</span><br><span class="line">4943 4951 4957 4967 4969 4973 4987 4993 4999</span><br></pre></td></tr></table></figure>


          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/07/20/%E6%A0%91%E3%80%81%E6%A3%AE%E6%9E%97%E4%B8%8E%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BD%AC%E6%8D%A2/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="LinRaise">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="LinRaise's Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2020/07/20/%E6%A0%91%E3%80%81%E6%A3%AE%E6%9E%97%E4%B8%8E%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BD%AC%E6%8D%A2/" itemprop="url">树、森林与二叉树的转换</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">Posted on</span>
              
              <time title="Post created" itemprop="dateCreated datePublished" datetime="2020-07-20T16:14:19+00:00">
                2020-07-20
              </time>
            

            
              <span class="post-meta-divider">|</span>
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-check-o"></i>
              </span>
              
                <span class="post-meta-item-text">Post modified&#58;</span>
              
              <time title="Post modified" itemprop="dateModified" datetime="2020-07-20T16:14:19+00:00">
                2020-07-20
              </time>
            
          </span>

          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>1、树转换为二叉树</p>
<p>由于二叉树是有序的，为了避免混淆，对于无序树，我们约定树中的每个结点的孩子结点按从左到右的顺序进行编号。</p>
<p>将树转换成二叉树的步骤是：<br>（1）加线。就是在所有兄弟结点之间加一条连线；<br>（2）抹线。就是对树中的每个结点，只保留他与第一个孩子结点之间的连线，删除它与其它孩子结点之间的连线；<br>（3）旋转。就是以树的根结点为轴心，将整棵树顺时针旋转一定角度，使之结构层次分明。</p>
<p><img src="/2020/07/20/%E6%A0%91%E3%80%81%E6%A3%AE%E6%9E%97%E4%B8%8E%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BD%AC%E6%8D%A2/20130916192154203" alt></p>
<p>树转换为二叉树的过程示意图</p>
<p>2、森林转换为二叉树</p>
<p>森林是由若干棵树组成，可以将森林中的每棵树的根结点看作是兄弟，由于每棵树都可以转换为二叉树，所以森林也可以转换为二叉树。</p>
<p>将森林转换为二叉树的步骤是：<br>（1）先把每棵树转换为二叉树；<br>（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点，用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树。</p>
<p><img src="/2020/07/20/%E6%A0%91%E3%80%81%E6%A3%AE%E6%9E%97%E4%B8%8E%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BD%AC%E6%8D%A2/20130916192200625" alt></p>
<p>森林转换为二叉树的转换过程示意图</p>
<p>3、二叉树转换为树</p>
<p>二叉树转换为树是树转换为二叉树的逆过程，其步骤是：<br>（1）若某结点的左孩子结点存在，将左孩子结点的右孩子结点、右孩子结点的右孩子结点……都作为该结点的孩子结点，将该结点与这些右孩子结点用线连接起来；<br>（2）删除原二叉树中所有结点与其右孩子结点的连线；<br>（3）整理（1）和（2）两步得到的树，使之结构层次分明。</p>
<p><img src="/2020/07/20/%E6%A0%91%E3%80%81%E6%A3%AE%E6%9E%97%E4%B8%8E%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BD%AC%E6%8D%A2/20130916192205156" alt><br>二叉树转换为树的过程示意图</p>
<p>4、二叉树转换为森林</p>
<p>二叉树转换为森林比较简单，其步骤如下：<br>（1）先把每个结点与右孩子结点的连线删除，得到分离的二叉树；<br>（2）把分离后的每棵二叉树转换为树；<br>（3）整理第（2）步得到的树，使之规范，这样得到森林。</p>
<p>根据树与二叉树的转换关系以及二叉树的遍历定义可以推知，树的先序遍历与其转换的相应的二叉树的先序遍历的结果序列相同；树的后序遍历与其转换的二叉树的中序遍历的结果序列相同；树的层序遍历与其转换的二叉树的后序遍历的结果序列相同。由森林与二叉树的转换关系以及森林与二叉树的遍历定义可知，森林的先序遍历和中序遍历与所转换得到的二叉树的先序遍历和中序遍历的结果序列相同。</p>
<p>6.6 哈夫曼树</p>
<p><strong>6.6.3哈夫曼树的应用</strong></p>
<p><strong>1．哈夫曼编码</strong></p>
<pre><code>通信中，可以采用0,1的不同排列来表示不同的字符，称为二进制编码。而哈夫曼树在数据编码中的应用，
是数据的最小冗余编码问题，它是数据压缩学的基础。若每个字符出现的频率相同，则可以采用等长的二进制编码，
若频率不同，则可以采用不等长的二进编码，频率较大的采用位数较少的编码，频率较小的字符采用位数较多的编码，
这样可以使字符的整体编码长度最小，这就是最小冗余编码的问题。 
而哈夫曼编码就是一种不等长的二进制编码，且哈夫曼树是一种最优二叉树，它的编码也是一种最优编码，
在哈夫曼树中，规定往左编码为0，往右编码为1，则得到叶子结点编码为从根结点到叶子结点中所有路径中0和1的顺序排列。  
例如，给定权{1,5,7,3}，得到的哈夫曼树及编码见图6-32 (假定权值就代表该字符名字)。</code></pre><p><img src="/2020/07/20/%E6%A0%91%E3%80%81%E6%A3%AE%E6%9E%97%E4%B8%8E%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BD%AC%E6%8D%A2/20130916192208546" alt></p>
<p><strong>2．哈夫曼译码</strong></p>
<pre><code>在通信中，若将字符用哈夫曼编码形式发送出去，对方接收到编码后，将编码还原成字符的过程，称为哈夫曼译码。</code></pre><p>树或森林与二叉树之间有一个自然的一一对应关系。任何一个森林或一棵树可惟一地对应到一棵二叉树;反之，任何一棵二叉树也能惟一地对应到一个森林或一棵树。</p>
<p><strong>1.树、森林到二叉树的转换</strong></p>
<p>(1)将树转换为二叉树</p>
<p>树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树：</p>
<p>①在所有兄弟结点之间加一连线;</p>
<p>②对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。</p>
<p>【例1】下面(a)图所示的树可转换为(c)图所示的二叉树。具体转换过程可</p>
<p>注意：</p>
<p>由于树根没有兄弟，故树转化为二叉树后，二叉树的根结点的右子树必为空。</p>
<p>(2)将一个森林转换为二叉树</p>
<p>具体方法是：</p>
<p>① 将森林中的每棵树变为二叉树</p>
<p>② 因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉</p>
<p>树。</p>
<p>【例2】下图中，左边包含三棵树的森林可转换为右边的二叉树。</p>
<p>　　<img src="/2020/07/20/%E6%A0%91%E3%80%81%E6%A3%AE%E6%9E%97%E4%B8%8E%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BD%AC%E6%8D%A2/20130916192211906" alt></p>
<p>具体转换过程可</p>
<p><strong>2.二叉树到树、森林的转换</strong></p>
<p>把二叉树转换到树和森林自然的方式是：若结点x是双亲y的左孩子，则把x的右孩子，右孩子的右孩子，…，都与y用连线连起来，</p>
<p>最后去掉所有双亲到右孩子的连线。</p>
<p>【例3】下图的森林就是由例2中二叉树转换成的。</p>
<p>​         <img src="/2020/07/20/%E6%A0%91%E3%80%81%E6%A3%AE%E6%9E%97%E4%B8%8E%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BD%AC%E6%8D%A2/20130916192125359" alt></p>
<p>具体转换过程可</p>
<p>哈夫曼算法</p>
<p> <img src="/2020/07/20/%E6%A0%91%E3%80%81%E6%A3%AE%E6%9E%97%E4%B8%8E%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BD%AC%E6%8D%A2/1062518-20161123012146846-665893972.png" alt="img"></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/07/17/%E5%8D%A1%E7%89%B9%E5%85%B0%E6%95%B0/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="LinRaise">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="LinRaise's Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2020/07/17/%E5%8D%A1%E7%89%B9%E5%85%B0%E6%95%B0/" itemprop="url">卡特兰数</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">Posted on</span>
              
              <time title="Post created" itemprop="dateCreated datePublished" datetime="2020-07-17T12:12:18+00:00">
                2020-07-17
              </time>
            

            
              <span class="post-meta-divider">|</span>
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-check-o"></i>
              </span>
              
                <span class="post-meta-item-text">Post modified&#58;</span>
              
              <time title="Post modified" itemprop="dateModified" datetime="2020-07-17T12:12:18+00:00">
                2020-07-17
              </time>
            
          </span>

          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>题目：一个栈的入栈序列是A、B、C、D、E，则栈的不可能的输出序列()</p>
<p>A、EDCBA       B、DECBA     <strong>C、DCEAB</strong>     D、ABCDE</p>
<p>题目从手工操作方面比较容易理解，需要借用一个辅助栈，先理一遍思路：</p>
<p>先看B答案：</p>
<p>(0)实始态</p>
<p>入栈序列是ABCDE</p>
<pre><code>i</code></pre><p>出栈序列是CDBEA</p>
<pre><code>j</code></pre><p>栈：|-</p>
<p>一开始有i,j两个下标指向入栈序和出栈序，我们需要C最先出栈，那么就应该让C处于当前栈顶的位置。</p>
<p>因此，需要将ABC入栈</p>
<p>（1）第一步</p>
<p>入栈序列是ABCDE</p>
<pre><code>i</code></pre><p>出栈序列是CDBEA</p>
<pre><code>j</code></pre><p>栈：|-ABC</p>
<p>栈顶为C,出栈序列的j位置为C,刚好可以匹配，因此j后移一位，从栈中弹出栈顶元素</p>
<p>（2）第二步</p>
<p>入栈序列是ABCDE</p>
<pre><code>i</code></pre><p>出栈序列是CDBEA</p>
<pre><code>j</code></pre><p>栈：|-AB</p>
<p>栈顶为B,出栈序列的j位置D,并不匹配，那么需要想办法使得栈顶元素为D.这时可以使入栈序列的i位置的字符继续进栈，期望使得栈顶元素为D。</p>
<p>（3）第三步</p>
<p>入栈序列是ABCDE</p>
<pre><code>i</code></pre><p>出栈序列是CDBEA</p>
<pre><code>j</code></pre><p>栈：|-ABD</p>
<p>栈顶为D,出栈序列的j位置为D,刚好可以匹配，因此j后移一位，从栈中弹出栈顶元素.</p>
<p>（4）第四步</p>
<p>入栈序列是ABCDE</p>
<pre><code>i</code></pre><p>出栈序列是CDBEA</p>
<pre><code>j</code></pre><p>栈：|-AB</p>
<p>栈顶为B,而出栈序列读头j下也是B,可以匹配，因此j后移一位，从栈中弹出栈顶元素。</p>
<p>（4）第四步</p>
<p>入栈序列是ABCDE</p>
<pre><code>i</code></pre><p>出栈序列是CDBEA</p>
<pre><code>j</code></pre><p>栈：|-A</p>
<p>栈顶为A,而出栈序列读头j下是E，不匹配，入栈序列的i位置的字符继续进栈。</p>
<p>（4）第五步</p>
<p>入栈序列是ABCDE</p>
<pre><code>i</code></pre><p>出栈序列是CDBEA</p>
<pre><code>j</code></pre><p>栈：|-AE</p>
<p>栈顶为E,而出栈序列读头j下也是E,可以匹配，因此j后移一位，从栈中弹出栈顶元素。</p>
<p>（4）第六步</p>
<p>入栈序列是ABCDE</p>
<pre><code>i</code></pre><p>出栈序列是CDBEA</p>
<pre><code>j</code></pre><p>栈：|-A</p>
<p>栈顶为A,而出栈序列读头j下是A，可以匹配，因此j后移一位，从栈中弹出栈顶元素。</p>
<p>入栈序列是ABCDE</p>
<pre><code>i</code></pre><p>出栈序列是CDBEA</p>
<pre><code>j</code></pre><p>栈：|-</p>
<p>匹配完成！</p>
<p>总结上面匹配过程的规律：</p>
<p>1.如果读头j能够从开头遍历到末尾，这说明可以成功匹配。</p>
<p>2.当栈顶元素和读头j下的元素相同时，匹配（弹出栈顶元素并且++j）</p>
<p>3.当栈顶元素和读头j下的元素不同时，失配，则入栈序列继续压栈，直至栈顶元素与读头j下元素匹配为止。</p>
<p>4.如果入栈序列一直压栈至最末尾尚未使得栈顶元素等于读头j元素时，说明出栈序列不能和入栈序列匹配。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;iostream&gt;</span><br><span class="line">#include&lt;stack&gt;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">bool isPopStack(char* pPushStack,char* pPopStack)</span><br><span class="line">&#123;</span><br><span class="line">	if( !pPushStack || !pPopStack ||strlen(pPushStack) !&#x3D;strlen(pPopStack))&#x2F;&#x2F;异常处理</span><br><span class="line">		return false;</span><br><span class="line">	stack&lt;char&gt; st;</span><br><span class="line">	while(*pPopStack !&#x3D; &#39;\0&#39;)</span><br><span class="line">	&#123;</span><br><span class="line">		&#x2F;&#x2F;如果前者成立，后者不会被判断，因此不会出现st为空却求st.top()的情况</span><br><span class="line">		while(st.empty() || st.top() !&#x3D; *pPopStack)</span><br><span class="line">		&#123;</span><br><span class="line">			if(*pPushStack &#x3D;&#x3D;&#39;\0&#39;)&#x2F;&#x2F;所有元素都已压栈还是找不到读头j下的元素说明序列不匹配</span><br><span class="line">				return false;</span><br><span class="line">			st.push(*pPushStack);</span><br><span class="line">			++pPushStack;</span><br><span class="line">		&#125;</span><br><span class="line">		&#x2F;&#x2F;!st.empty() &amp;&amp; st.top() &#x3D;&#x3D;*pPopStack</span><br><span class="line">		st.pop();</span><br><span class="line">		++pPopStack;</span><br><span class="line">	&#125;</span><br><span class="line">	return true;</span><br><span class="line">&#125;</span><br><span class="line">void main()</span><br><span class="line">&#123;</span><br><span class="line">	char pPushStack[]&#x3D;&quot;ABCDE&quot;;</span><br><span class="line">	char pPopStack[]&#x3D;&quot;CDBEA&quot;;</span><br><span class="line">	cout&lt;&lt;&quot;pPopStack是否是pPushStack的弹栈序列? (1 or 0) :&quot;</span><br><span class="line">		&lt;&lt;isPopStack(pPushStack,pPopStack)&lt;&lt;endl;</span><br><span class="line">	&#x2F;&#x2F;A、EDCBA       B、DECBA     C、DCEAB     D、ABCDE</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<p>卡特兰数经典应用(腾讯面试题)：有6个同学去图书馆借还书，书名是《算法导论》。馆中已经没有《算法导论》的存书了。有3个同学是去还书的，有3个同学是去借书的。现在请问，6位同学有多少种借还书的顺序方案可以保证去借书的同学都能借到《算法导论》？</p>
<p>解释：抽象化题目，同学可以用1,2,3,4,5,6表示．还书可以用压栈表示，借书可以用弹栈表示，借还书方案可以表示为弹栈的所有方式．</p>
<p>因此这是另外一种问法：</p>
<p>一个栈的进栈序列为1，2，3，…，n，有多少种不同的出栈序列?</p>
<p>分析：对于每一个数来说，必须进栈一次，出栈一次．我们把进栈设为1，出栈设为-1。n个数的进栈出栈顺序可以组成2n位组合序列a1,a2,a3,a4……．</p>
<p>假设n=4(等待入栈的顺序是1，2，3，4)</p>
<p>则其中一个进出栈顺序可以表示为1 , 1 , 1 , 1,-1,-1,-1,-1.即“进进进进出出出出”。这是一种进出栈的方式。</p>
<p>2n位二进制数序列需要保证两个条件成立：</p>
<p>1 .由n个1和n个-1组成（有多少个数进栈就应该有多少个数出栈）。</p>
<p>2.从左往右扫描到的每一位k，在k（包括k）之前1的总数必须大于或等于-1的总数（即进栈的个数要比出栈的个数多，不允许出现栈空却要出栈的情况）</p>
<p>在2n位二进制数中填入n个1的方案数为,不填1的其余n位自动填-1。从中减去不符合要求（由左而右扫描，-1的总数大于1的总数）的方案数即为所求。</p>
<p>接下来的任务就是找不符合要求的方案数了，这是难点。对于一个不合要求的序列，我们假设有一个最小的k令a1+a2+a3+……+ak&lt;0。由于这里k是最小的，所以必有a1+a2+a3+……+ak＝-1。并且k是奇数，(注：因为k个(1,-1)相加结果是-1,必定是-1比1多1个.若1有m个,则-1有m+1个,总数=2m+1)。</p>
<p>不妨设k=2m+1,则a1,a2…ak中有m+1个-1和m个1.</p>
<p>此后的2n-(2m+1)位有n-(m+1)个-1和n-m个1。如果将后2n-(2m+1)位的0和1置换，使之变成n-(m+1)个1和n-m个－1。结果有n+1个-1和n-1个1。即一个不合要求的序列对应一个由n+1个0和n-1个1组成的排列。</p>
<p>反过来，任何一个由n+1个0和n-1个1组成的2n位二进制数，由于-1的个数多2个，2n为偶数，故必在某一个奇数位上出现-1的累计数超过1的累计数。（不合要求的序列）同样在后面部分-1和1互换，使之成为由n个-1和n个1组成的2n位数，即n+1个-1和n-1个1组成的2n位数必对应一个不符合要求的序列。</p>
<p>因而不合要求的2n位数与n+1个0，n－1个1组成的排列一一对应。</p>
<p>显然，不符合要求的方案数为c(2n,n+1)。由此得出输出序列的总数目=-c(2n,n+1)=/(n+1)=h(n+1)。</p>
<p>小结：</p>
<ol>
<li><p>对于n个元素的进出栈顺序，由于每个元素都各进出一次，我们可以用2n位表示n个元素的进出栈序列。</p>
</li>
<li><p>进栈记为1,出栈记为-1，则2n位有n位为1,n位为-1,总共的组合数有</p>
</li>
<li><p>在总共的组合序中有一部分序列不满足要求（栈已经为空却硬要出栈），因此我们需要减去这一部分不合要求的序列数。</p>
</li>
</ol>
<p>a1,a2,a3,a4……..a2n中假设有最小的k满足a1,a2,a3,………..ak&lt;0(不合要求的序列)，因k已最小，ak=-1,a1+a2+…+ak-1=0,所以k为奇数k=2m+1,前边有m+1个-1，m个1。将此后n-k个数-1，1置换,则后面有n-m-1个1,n-m个-1.前后总共有n-1个1,n+1个-1.因此，每一个不合要求的序列都和有n-1个1,n+1个-1的2n位二进制数对应</p>
<p>继续证明反之也成立。一个n-1个1,n+1个-1的2n位二进制数是否与和一个不合要求的序列（n个1,n个-1）相对应？由于-1比1多2个，整个序列加起来为-2，则必然存在一个最小k使得某一部分序列a1+a2+a3++..+ak&lt;0(实质上等于-1，并且k不是末尾，否则=-2)，同理k为奇数。则将k后面的数-1,1置换，则总共会有n个1和n个-1。则每一个n-1个1，n+1个-1的2n位二进制数都与一个不合要求的序列(a1+a2+..ak&lt;0且-1,1个数都为n)对应，故证。</p>
<p><img src="/2020/07/17/%E5%8D%A1%E7%89%B9%E5%85%B0%E6%95%B0/SouthEast" alt="img"></p>
<p>最后给出卡特兰公式:H(n)=-C(2n,n+1)</p>
<p>一个栈的进栈序列为1，2，3，…，n，有多少种不同的出栈序列?</p>
<p>重新回到这道题上面来，下面的程序基于卡特兰公式的思路。</p>
<p>1,2,3……n可以用2n位表示入栈出栈序列。在2n位中填入n个1，有C2n,n种办法，可以联想到字符串组合的程序</p>
<p>对于当前索引index,如果index选择填1，则只需要在余下的2n-1中填入n-1个1，如果index不选择填入1，则需要在余下的2n-1中填入n个1.可以用递归实现。</p>
<p>再写一个子函数判断这是否可以组成弹栈序列，只需要一直累加和&gt;=0则表示可组成，否则不是一个弹栈序列。</p>
<p>再写一个输出函数即可。时间效率上是指数级的。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;iostream&gt;</span><br><span class="line">#include&lt;vector&gt;</span><br><span class="line">#include&lt;stack&gt;</span><br><span class="line">using namespace std;</span><br><span class="line">&#x2F;***********************************************</span><br><span class="line">判断字符串组合是否可以构成一个压栈弹栈序列</span><br><span class="line">************************************************&#x2F;</span><br><span class="line">bool IsPopQueue(vector&lt;int&gt;&amp; result )</span><br><span class="line">&#123;</span><br><span class="line">	int Sum &#x3D; 0 ;</span><br><span class="line">	vector&lt;int&gt;::iterator iter &#x3D; result.begin();</span><br><span class="line">	for(; iter &lt; result.end(); ++ iter)</span><br><span class="line">	&#123;</span><br><span class="line">		Sum +&#x3D;*iter;</span><br><span class="line">		if(Sum &lt; 0) &#x2F;&#x2F;a1+a2+a3+..+ak &lt; 0则不符合要求</span><br><span class="line">			return false;</span><br><span class="line">	&#125;</span><br><span class="line">	return true;</span><br><span class="line">&#125;</span><br><span class="line">&#x2F;&#x2F;输出弹栈序列</span><br><span class="line">void PrintPopQueue(vector&lt;int&gt;&amp; result )</span><br><span class="line">&#123;</span><br><span class="line">	stack&lt;int&gt; Stack; </span><br><span class="line">	int Index&#x3D;1;</span><br><span class="line">	for(int i &#x3D; 0 ; i &lt; result.size(); ++ i)</span><br><span class="line">	&#123;</span><br><span class="line">		if( result[i] &#x3D;&#x3D; 1)</span><br><span class="line">			Stack.push(Index++);</span><br><span class="line">		else</span><br><span class="line">		&#123;</span><br><span class="line">			cout&lt;&lt;&#39; &#39;&lt;&lt;Stack.top();</span><br><span class="line">			Stack.pop();</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line">&#x2F;***********************************************</span><br><span class="line">字符串组合</span><br><span class="line">************************************************&#x2F;</span><br><span class="line">void Combination(int Index, int number, vector&lt;int&gt;&amp; result)</span><br><span class="line">&#123;</span><br><span class="line">	static int count&#x3D;0;</span><br><span class="line">	if(number &#x3D;&#x3D; 0)</span><br><span class="line">	&#123;</span><br><span class="line">		if(IsPopQueue(result))</span><br><span class="line">		&#123;</span><br><span class="line">			++count;</span><br><span class="line">			vector&lt;int&gt;::iterator iter &#x3D; result.begin();</span><br><span class="line">			for(; iter &lt; result.end(); ++ iter)</span><br><span class="line">				printf(&quot;%d &quot;, *iter);</span><br><span class="line">			PrintPopQueue(result);</span><br><span class="line">			printf(&quot;  %d \n&quot;,count);</span><br><span class="line">		&#125;</span><br><span class="line">		return;</span><br><span class="line">	&#125;</span><br><span class="line">	if(Index &lt; 0)</span><br><span class="line">	    return;</span><br><span class="line">	result[Index] &#x3D; 1 ;</span><br><span class="line">	Combination( Index-1 , number - 1, result);</span><br><span class="line">	result[Index] &#x3D; -1 ;</span><br><span class="line">	Combination( Index-1 , number, result);</span><br><span class="line">&#125;</span><br><span class="line">void main()</span><br><span class="line">&#123;</span><br><span class="line">	vector&lt;int&gt; Result(8,-1);</span><br><span class="line">	Combination(7,4,Result);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>另外一种思考方式。根据栈中的状态和Vector中的状态，可以有两种先择，一种选择是将Vector中的值压到栈中去，Vector中的索引后移一位，继续递归下降调用。另一种选择是将Stack顶元素弹到Result中保存起来，继续递归下降调用。具体实现见代码。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;iostream&gt;</span><br><span class="line">#include&lt;stack&gt;</span><br><span class="line">#include&lt;vector&gt;</span><br><span class="line">using namespace std;</span><br><span class="line">void Combination(stack&lt;int&gt;&amp; Stack,vector&lt;int&gt;&amp; Vec,int Index,vector&lt;int&gt;&amp; Result)</span><br><span class="line">&#123;</span><br><span class="line">	if(Vec.size() &lt; 1)</span><br><span class="line">		return ;</span><br><span class="line">	&#x2F;&#x2F;如果栈空且Index遍历到了末尾，这说明，Result中已经保存了Vec中的所有数</span><br><span class="line">	if(Stack.empty() &amp;&amp; Vec.size() &#x3D;&#x3D; Index)</span><br><span class="line">	&#123;</span><br><span class="line">		for(int i&#x3D;0;i&lt;Result.size();++i)</span><br><span class="line">			cout&lt;&lt;Result[i]&lt;&lt;&quot; &quot;;</span><br><span class="line">		cout&lt;&lt;endl;</span><br><span class="line">		return ;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	&#x2F;&#x2F;!Stack.empty() || Vec.size() !&#x3D;Index</span><br><span class="line">	if(!Stack.empty())&#x2F;&#x2F;分两条分支，一条为将栈中值弹到Result中</span><br><span class="line">	&#123;</span><br><span class="line">		int Temp&#x3D;Stack.top();</span><br><span class="line">		Result.push_back(Temp);</span><br><span class="line">		Stack.pop();</span><br><span class="line">	 </span><br><span class="line">		Combination(Stack,Vec,Index,Result);</span><br><span class="line">	 </span><br><span class="line">		Stack.push(Temp);</span><br><span class="line">		Result.pop_back();</span><br><span class="line">	&#125;	</span><br><span class="line">	&#x2F;&#x2F;Stack.empty() &amp;&amp; Vec.size() !&#x3D;Index</span><br><span class="line">	if(Vec.size() !&#x3D; Index)</span><br><span class="line">	&#123;</span><br><span class="line">		Stack.push(Vec[Index]);</span><br><span class="line">		&#x2F;&#x2F;分两条分支，一条为将Vec[Index]中的值压进栈</span><br><span class="line">		Combination(Stack,Vec,Index+1,Result);</span><br><span class="line">		Stack.pop();</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()</span><br><span class="line">&#123;</span><br><span class="line">	vector&lt;int&gt; Vec;</span><br><span class="line">	Vec.push_back(1);</span><br><span class="line">	Vec.push_back(2);</span><br><span class="line">	Vec.push_back(3);</span><br><span class="line">	Vec.push_back(4);</span><br><span class="line">	stack&lt;int&gt; Stack;</span><br><span class="line">	vector&lt;int&gt; Result;</span><br><span class="line">	Combination(Stack,Vec,0,Result);</span><br><span class="line">	return 0 ;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<p>或者</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br></pre></td><td class="code"><pre><span class="line">#include &lt;iostream&gt;</span><br><span class="line">#include &lt;vector&gt;</span><br><span class="line">#include &lt;iomanip&gt;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">void Combination(int A[], int Index, int ALen, vector&lt;int&gt;&amp; Stack, vector&lt;int&gt;&amp; Queue)</span><br><span class="line">&#123;</span><br><span class="line">	static int count &#x3D; 0;</span><br><span class="line">	if (Index &#x3D;&#x3D; ALen)</span><br><span class="line">	&#123;</span><br><span class="line">		cout &lt;&lt; ++count &lt;&lt; &quot;: &quot;;</span><br><span class="line">		for (unsigned int k &#x3D; 0; k &lt; Queue.size(); k++)</span><br><span class="line">		&#123;</span><br><span class="line">			cout &lt;&lt; setw(5) &lt;&lt; Queue[k];</span><br><span class="line">		&#125;</span><br><span class="line">		for (int k &#x3D; Stack.size() - 1; k &gt;&#x3D; 0; k--)</span><br><span class="line">		&#123;</span><br><span class="line">			cout &lt;&lt; setw(5) &lt;&lt; Stack[k];</span><br><span class="line">		&#125;</span><br><span class="line">		cout &lt;&lt; endl;</span><br><span class="line">		return;</span><br><span class="line">	&#125;</span><br><span class="line">	&#x2F;&#x2F;Index !&#x3D;ALen</span><br><span class="line">	Stack.push_back(A[Index]); </span><br><span class="line">	Combination(A, Index + 1, ALen, Stack, Queue);\</span><br><span class="line">	Stack.pop_back(); </span><br><span class="line">	if (!Stack.empty())</span><br><span class="line">	&#123;</span><br><span class="line">		Queue.push_back(Stack.back());</span><br><span class="line">		Stack.pop_back();</span><br><span class="line">		Combination(A, Index, ALen, Stack, Queue); </span><br><span class="line">		Stack.push_back(Queue[Queue.size() - 1]);	</span><br><span class="line">		Queue.pop_back();</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()</span><br><span class="line">&#123;</span><br><span class="line">	int A[] &#x3D; &#123;1, 2, 3, 4&#125;;</span><br><span class="line">	vector&lt;int&gt; Stack;</span><br><span class="line">	vector&lt;int&gt; Queue;</span><br><span class="line">	Combination(A, 0, sizeof(A) &#x2F; sizeof(int),	Stack, Queue);</span><br><span class="line">	return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>实训：<a href="http://acm.hdu.edu.cn/showproblem.php?pid=1515" target="_blank" rel="noopener">http://acm.hdu.edu.cn/showproblem.php?pid=1515</a></p>
<p>Problem Description</p>
<p>How can anagrams result from sequences of stack operations? There are two sequences of stack operators which can convert TROT to TORT: </p>
<p> [</p>
<p>i i i i o o o o</p>
<p>i o i i o o i o</p>
<p>]</p>
<p>where i stands for Push and o stands for Pop. Your program should, given pairs of words produce sequences of stack operations which convert the first word to the second.</p>
<p>A stack is a data storage and retrieval structure permitting two operations: </p>
<p>Push - to insert an item and</p>
<p>Pop - to retrieve the most recently pushed item </p>
<p>We will use the symbol i (in) for push and o (out) for pop operations for an initially empty stack of characters. Given an input word, some sequences of push and pop operations are valid in that every character of the word is both pushed and popped, and furthermore, no attempt is ever made to pop the empty stack. For example, if the word FOO is input, then the sequence: </p>
<p>i i o i o o is valid, but </p>
<p>i i o is not (it’s too short), neither is </p>
<p>i i o o o i (there’s an illegal pop of an empty stack) </p>
<p>Valid sequences yield rearrangements of the letters in an input word. For example, the input word FOO and the sequence i i o i o o produce the anagram OOF. So also would the sequence i i i o o o. You are to write a program to input pairs of words and output all the valid sequences of i and o which will produce the second member of each pair from the first.</p>
<p>题目很多英文，看了半小时才明白题目要求做什么，英语水平不好很吃亏．题目大致要求是：给出两个字串str1,str2,利用一个栈，找出有多少种方法(即进栈出栈操作．)可以从str1得到str2.先看看状态转移有哪些．</p>
<p>(１)如果str1和str2包含有不同的字符，或者长度不一，或者相同字符数目不同，则我们可以不做任何操作，直接返回false.就是sort(str1),sort(str2),if(str1!=str2) do nothing.</p>
<p>如果通过第(１)步的检测，则开始看状态转移：<strong>(str1中的字符进栈和栈顶元素出栈)</strong></p>
<p><img src="/2020/07/17/%E5%8D%A1%E7%89%B9%E5%85%B0%E6%95%B0/SouthEast-2" alt="img"></p>
<p>(２)<strong>进栈！</strong>如果str1中当前字符索引index还没有到末尾，即str1还有字符未处理完毕，则str1[index]可以选择进栈．(栈为空，str1[index]可以进栈，栈不空，一样可以进栈，str1[index]!=str2[rIndex],可以进栈，str1[index]==str2[rIndex],可以进栈，stack.top==str2[rIndex]可以进栈，因为虽然当前栈顶元素和str2[rIndex]相等，但是一样可以进栈是因为后续进栈的元素还有可能等于str2[rIndex],stack.top!=str2[rIndex]可以进栈,所以str1[index]的进栈只要str1尚未处理完就可以进行．)</p>
<p>(３)<strong>出栈！</strong>如果栈不为空而且栈顶元素等于str2[rIndex]才可以出栈(表示匹配．)这个很容易理解．</p>
<p>利用(２)(３)的状态转移就可以写出递归函数，<strong>当然因为使用的是全局堆栈，所以，需要记住还原现场</strong>．</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br></pre></td><td class="code"><pre><span class="line">#include &lt;iostream&gt;</span><br><span class="line">#include&lt;string&gt;</span><br><span class="line">#include&lt;stack&gt;</span><br><span class="line">#include &lt;algorithm&gt;</span><br><span class="line">#include &lt;vector&gt;</span><br><span class="line">using namespace std;</span><br><span class="line">string str1,str2;</span><br><span class="line">vector&lt;char&gt; result;</span><br><span class="line">stack&lt;char&gt; st;</span><br><span class="line">void Combination(int index,int rIndex)</span><br><span class="line">&#123;</span><br><span class="line">	if( rIndex &#x3D;&#x3D; str2.length())</span><br><span class="line">	&#123;</span><br><span class="line">		for(int i&#x3D;0;i&lt;result.size();++i)</span><br><span class="line">			cout&lt;&lt;result[i]&lt;&lt;&#39; &#39;;</span><br><span class="line">		cout&lt;&lt;endl;</span><br><span class="line">		return ;</span><br><span class="line">	&#125;</span><br><span class="line">	if( index &lt; str1.length())&#x2F;&#x2F;str1的字符还没有处理完，则可以选择压栈，第2分支</span><br><span class="line">	&#123;</span><br><span class="line">		result.push_back(&#39;i&#39;);</span><br><span class="line">		st.push(str1[index]);&#x2F;&#x2F;2</span><br><span class="line">		Combination(index+1,rIndex);</span><br><span class="line">		st.pop();&#x2F;&#x2F;recover</span><br><span class="line">		result.pop_back();&#x2F;&#x2F;recover</span><br><span class="line">	&#125;</span><br><span class="line">	if( !st.empty() &amp;&amp; st.top() &#x3D;&#x3D;str2[rIndex])&#x2F;&#x2F;栈不为空且栈顶元素等于str2[rIndex]，可以选择弹栈,第2分支</span><br><span class="line">	&#123;</span><br><span class="line">		result.push_back(&#39;o&#39;);</span><br><span class="line">		char temp&#x3D;st.top();</span><br><span class="line">		st.pop();&#x2F;&#x2F;</span><br><span class="line">		Combination(index,rIndex+1);</span><br><span class="line">		result.pop_back();&#x2F;&#x2F;recover </span><br><span class="line">		st.push(temp);&#x2F;&#x2F;recover </span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()</span><br><span class="line">&#123;</span><br><span class="line">	while(cin&gt;&gt;str1&gt;&gt;str2)</span><br><span class="line">	&#123;</span><br><span class="line">		cout&lt;&lt;&#39;[&#39;&lt;&lt;endl;</span><br><span class="line">		if(str2.length()&#x3D;&#x3D;str1.length())</span><br><span class="line">		&#123;</span><br><span class="line">			string t1&#x3D;str1, t2&#x3D;str2;</span><br><span class="line">			sort(t1.begin(), t1.end());</span><br><span class="line">			sort(t2.begin(), t2.end());</span><br><span class="line">			if(t1&#x3D;&#x3D;t2)&#x2F;&#x2F;if the two string have the same char,then go ahead.</span><br><span class="line">			&#123;</span><br><span class="line">				Combination(0,0);</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		cout&lt;&lt;&#39;]&#39;&lt;&lt;endl;</span><br><span class="line">	&#125;</span><br><span class="line">	return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<p>卡特兰练兵场：HDU2067小兔的棋盘</p>
<p>小兔的棋盘</p>
<p>Problem Description</p>
<p>小兔的叔叔从外面旅游回来给她带来了一个礼物，小兔高兴地跑回自己的房间，拆开一看是一个棋盘，小兔有所失望。不过没过几天发现了棋盘的好玩之处。从起点(0，0)走到终点(n,n)的最短路径数是C(2n,n),现在小兔又想如果不穿越对角线(但可接触对角线上的格点)，这样的路径数有多少?小兔想了很长时间都没想出来，现在想请你帮助小兔解决这个问题，对于你来说应该不难吧!</p>
<p>Input</p>
<p>每次输入一个数n(1&lt;=n&lt;=35)，当n等于－1时结束输入。</p>
<p>Output 对于每个输入数据输出路径数，具体格式看Sample。</p>
<p>Sample Input 1</p>
<p>3</p>
<p>12</p>
<p>-1</p>
<p>Sample Output 1 1 2</p>
<p>2 3 10</p>
<p>3 12 416024</p>
<p>解释：</p>
<p>维基百科上卡特兰数可以用两个式子推导Click me~wikipedia。</p>
<p>第一个式子用__int64刚好不溢出，而第二个式子需要用java的大数类来解决，下面给出代码：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br></pre></td><td class="code"><pre><span class="line">#include &lt;iostream&gt;</span><br><span class="line">using namespace std;</span><br><span class="line">const int MAX &#x3D; 40;</span><br><span class="line"></span><br><span class="line">&#x2F;&#x2F;http:&#x2F;&#x2F;zh.wikipedia.org&#x2F;wiki&#x2F;%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0</span><br><span class="line"></span><br><span class="line">__int64 Catalan[MAX];</span><br><span class="line"></span><br><span class="line">int main()</span><br><span class="line">&#123;</span><br><span class="line">	Catalan[0] &#x3D; Catalan[1] &#x3D; 1;</span><br><span class="line">	int i,j;</span><br><span class="line">	__int64 sum;</span><br><span class="line">	for (i&#x3D;2; i&lt;MAX; ++i)</span><br><span class="line">	&#123;</span><br><span class="line">		sum &#x3D; 0;</span><br><span class="line">		for (j&#x3D;0; j&lt;i; ++j)</span><br><span class="line">		&#123;</span><br><span class="line">			sum +&#x3D; Catalan[j] * Catalan[i-j-1];</span><br><span class="line">		&#125;</span><br><span class="line">		Catalan[i] &#x3D; sum;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	int t &#x3D; 1,n;</span><br><span class="line">	while( cin &gt;&gt; n &amp;&amp; n!&#x3D;-1 )</span><br><span class="line">	&#123;</span><br><span class="line">		printf(&quot;%d %d %I64d\n&quot;,t++,n,Catalan[n]*2);</span><br><span class="line">	&#125;</span><br><span class="line">	return 0;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;iostream&gt;</span><br><span class="line">#include&lt;cstdio&gt;</span><br><span class="line">using namespace std;</span><br><span class="line">__int64 c[36]&#x3D;&#123;</span><br><span class="line">1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, </span><br><span class="line">2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, </span><br><span class="line">24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, </span><br><span class="line">18367353072152, 69533550916004, 263747951750360, 1002242216651368,</span><br><span class="line"> 3814986502092304, 14544636039226909, 55534064877048198, 212336130412243110,</span><br><span class="line">  812944042149730764, 3116285494907301262  &#125;;</span><br><span class="line">int main()</span><br><span class="line">&#123;</span><br><span class="line">    int n;</span><br><span class="line">    int flag&#x3D;1;</span><br><span class="line">    while(cin&gt;&gt;n&amp;&amp;n!&#x3D;-1)</span><br><span class="line">    &#123;</span><br><span class="line">        printf(&quot;%d %d %I64d\n&quot;,flag++,n,c[n]*2);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    return 0;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<p>蹩脚的java又要献丑了</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line">import java.io.*;</span><br><span class="line">import java.math.*;</span><br><span class="line">import java.util.*;</span><br><span class="line"></span><br><span class="line">public class Main </span><br><span class="line">&#123;</span><br><span class="line">    public static void main(String[] args) </span><br><span class="line">    &#123;</span><br><span class="line">        Scanner cin &#x3D; new Scanner(System.in);</span><br><span class="line">        Integer N &#x3D; 36, i,t &#x3D; 1;</span><br><span class="line">        BigInteger[] cat &#x3D; new BigInteger[N];</span><br><span class="line"></span><br><span class="line">        cat[0] &#x3D; cat[1] &#x3D; BigInteger.valueOf(1);</span><br><span class="line">        for (i &#x3D; 2; i &lt; N; ++i) </span><br><span class="line">        &#123;</span><br><span class="line">            cat[i] &#x3D; cat[i - 1].multiply(BigInteger.valueOf(i * 4 - 2)).divide(BigInteger.valueOf(i + 1));</span><br><span class="line">        &#125;</span><br><span class="line">     </span><br><span class="line">        while (cin.hasNext()) </span><br><span class="line">        &#123;</span><br><span class="line">            i &#x3D; cin.nextInt();</span><br><span class="line">            if (i &#x3D;&#x3D; -1)</span><br><span class="line">                break;</span><br><span class="line">            System.out.println(t++ + &quot; &quot; + i + &quot; &quot; + cat[i].multiply(BigInteger.valueOf(2)));</span><br><span class="line">        &#125;</span><br><span class="line">     </span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<p>参考资料：</p>
<p><a href="http://baike.baidu.com/view/2499752.htm" target="_blank" rel="noopener">http://baike.baidu.com/view/2499752.htm</a></p>
<p><a href="http://www.cnblogs.com/muzinian/archive/2012/11/08/2761430.html" target="_blank" rel="noopener">http://www.cnblogs.com/muzinian/archive/2012/11/08/2761430.html</a></p>
<p><a href="http://zh.wikipedia.org/wiki/%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0" target="_blank" rel="noopener">http://zh.wikipedia.org/wiki/%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0</a></p>

          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2020/07/16/%E4%BA%8C%E5%8F%89%E6%A0%91/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="LinRaise">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="LinRaise's Blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/2020/07/16/%E4%BA%8C%E5%8F%89%E6%A0%91/" itemprop="url">二叉树</a></h1>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">Posted on</span>
              
              <time title="Post created" itemprop="dateCreated datePublished" datetime="2020-07-16T12:43:58+00:00">
                2020-07-16
              </time>
            

            
              <span class="post-meta-divider">|</span>
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-check-o"></i>
              </span>
              
                <span class="post-meta-item-text">Post modified&#58;</span>
              
              <time title="Post modified" itemprop="dateModified" datetime="2020-07-16T12:43:58+00:00">
                2020-07-16
              </time>
            
          </span>

          

          
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p>序:二叉树作为树的一种，是一种重要的数据结构,常见的二叉树有:<br>满二叉树:除叶子结点外,所有结点都有两个结点,叶子结点的left,right为NULL.<br>哈夫曼树：又称为最优二叉数，是一种带权路径最短的树。哈夫曼编码就是哈夫曼树的应用,可以用来进行编码压缩.哈夫曼树的构造见哈夫曼树的构造<br>完全二叉树:除了最底层的叶子结点之外,其余层全满,而且叶子层集中在左端.堆是一种特殊的完全二叉树(全满或者差一个结点就全满)<br>平衡二叉树：所谓平衡二叉树指的是，左右两个子树的高度差的绝对值不超过 1。包括AVL树,红黑树.<br>红黑树：具体见红黑树问题<br>下面是我总结的这几天看过的一些常见二叉树问题.</p>
<p>1.二叉搜索树的迭代构造<br>二叉搜索树是一棵排好序的树,当新插入一个节点的时候,小于当前根结点左走,大于当前根结点右走,直至走到NULL点,就是该结点的位置.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line">void IterativeInsert(Tree* T,node* z)&#x2F;&#x2F;插入节点  </span><br><span class="line">&#123;  </span><br><span class="line">    node* y&#x3D;NULL;  </span><br><span class="line">    node* x&#x3D;T-&gt;root;&#x2F;&#x2F;管理两个指针，父指针y,y的子树指针x  </span><br><span class="line">    while(x!&#x3D;NULL)&#x2F;&#x2F;一直向下遍历到z应该插入的位置  </span><br><span class="line">    &#123;  </span><br><span class="line">        y&#x3D;x;  </span><br><span class="line">        if(x-&gt;value &lt; z-&gt;value)  </span><br><span class="line">            x&#x3D;x-&gt;right;  </span><br><span class="line">        else x&#x3D;x-&gt;left;  </span><br><span class="line">    &#125;  </span><br><span class="line">    z-&gt;p&#x3D;y;&#x2F;&#x2F;先将z的父指针p指向y  </span><br><span class="line">    if(y&#x3D;&#x3D;NULL)&#x2F;&#x2F;若树为空，树根即为z  </span><br><span class="line">        T-&gt;root&#x3D;z;  </span><br><span class="line">    else if(z-&gt;value &lt; y-&gt;value)&#x2F;&#x2F;否则分插入左边还是右边  </span><br><span class="line">        y-&gt;left&#x3D;z;  </span><br><span class="line">    else y-&gt;right&#x3D;z;  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<p>2.二叉搜索树的递归构造<br>1.若是空树,则插入至根结点位置</p>
<p>2.若比当前根点,插入左边.</p>
<p>3.否则插入右边</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">node* TreeInsert(node* root,node* z)</span><br><span class="line">&#123;</span><br><span class="line">	if(!root)</span><br><span class="line">		root&#x3D;z;</span><br><span class="line">	else if(root-&gt;value &lt; z-&gt;value)</span><br><span class="line">		root-&gt;right&#x3D;TreeInsert(root-&gt;right,z);</span><br><span class="line">	else root-&gt;left&#x3D;TreeInsert(root-&gt;left,z);</span><br><span class="line">	return root;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>3.二叉树三种递归遍历方式.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line">void InorderTreeWalk(node* root)</span><br><span class="line">&#123;</span><br><span class="line">	if(!root ) return ;</span><br><span class="line">	InorderTreeWalk(root-&gt;left);</span><br><span class="line">	cout&lt;&lt;root-&gt;value&lt;&lt;&#39; &#39;;</span><br><span class="line">	InorderTreeWalk(root-&gt;right);</span><br><span class="line">&#125;</span><br><span class="line">void PriorTreeWalk(node* root)</span><br><span class="line">&#123;</span><br><span class="line">	if(!root ) return ;</span><br><span class="line">	cout&lt;&lt;root-&gt;value&lt;&lt;&#39; &#39;;</span><br><span class="line">	PriorTreeWalk(root-&gt;left);</span><br><span class="line">	PriorTreeWalk(root-&gt;right);</span><br><span class="line">&#125;</span><br><span class="line">void PostTreeWalk(node* root)</span><br><span class="line">&#123;</span><br><span class="line">	if(!root ) return ;</span><br><span class="line">	PostTreeWalk(root-&gt;left);</span><br><span class="line">	PostTreeWalk(root-&gt;right);</span><br><span class="line">	cout&lt;&lt;root-&gt;value&lt;&lt;&#39; &#39;;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>4.二叉树三种迭代遍历方式.<br>深度优先原则,输出顺序是’左子树优先’</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br></pre></td><td class="code"><pre><span class="line">void IterativeInorderWalk(node *root)&#x2F;&#x2F;迭代中序遍历  </span><br><span class="line">&#123;  </span><br><span class="line">    node* p&#x3D;root;  </span><br><span class="line">    stack&lt;node*&gt; st;&#x2F;&#x2F;利用栈  </span><br><span class="line">    if(!p)  &#x2F;&#x2F;if(!p)&#x3D;if(p&#x3D;&#x3D;null)</span><br><span class="line">        return ;  </span><br><span class="line">    while(p || !st.empty())&#x2F;&#x2F;当p不为空 或者st不为空  </span><br><span class="line">    &#123;  </span><br><span class="line">        while(p)&#x2F;&#x2F;沿着左孩子方向走到最左下。同时压栈  </span><br><span class="line">        &#123;  </span><br><span class="line">            st.push(p);  </span><br><span class="line">            p&#x3D;p-&gt;left;  </span><br><span class="line">        &#125;  </span><br><span class="line">        p&#x3D;st.top();&#x2F;&#x2F;获取栈顶元素  </span><br><span class="line">        cout&lt;&lt;p-&gt;value&lt;&lt;&quot; &quot;;  </span><br><span class="line">        st.pop();  </span><br><span class="line">        p&#x3D;p-&gt;right;  </span><br><span class="line">    &#125;  </span><br><span class="line">&#125;  </span><br><span class="line"></span><br><span class="line">void IterativePriorTreeWalk(node* root)&#x2F;&#x2F;迭代先序遍历  </span><br><span class="line">&#123;  </span><br><span class="line">    node* p&#x3D;root;  </span><br><span class="line">    stack&lt;node* &gt; st;  </span><br><span class="line">    if(!p)   </span><br><span class="line">        return ;  </span><br><span class="line">    while(p || !st.empty())  </span><br><span class="line">    &#123;  </span><br><span class="line">        while(p)  </span><br><span class="line">        &#123;  </span><br><span class="line">            cout&lt;&lt;p-&gt;value&lt;&lt;&quot; &quot;;  </span><br><span class="line">            st.push(p);  </span><br><span class="line">            p&#x3D;p-&gt;left;  </span><br><span class="line">        &#125;  </span><br><span class="line">        p&#x3D;st.top();  </span><br><span class="line">        st.pop();  </span><br><span class="line">        p&#x3D;p-&gt;right;  </span><br><span class="line">    &#125;  </span><br><span class="line">&#125;  </span><br><span class="line"></span><br><span class="line">void IterativePostWalk(node* root)  </span><br><span class="line">&#123;  </span><br><span class="line">    node* p&#x3D;root;  </span><br><span class="line">    stack&lt;node* &gt; st;  </span><br><span class="line">    node* pre&#x3D;NULL;&#x2F;&#x2F;pre表示最近一次访问的结点  </span><br><span class="line">    if(!p) return ;  </span><br><span class="line">    while(p || !st.empty())  </span><br><span class="line">    &#123;  </span><br><span class="line">        while(p)    &#x2F;&#x2F;沿着左孩子方向走到最左下  </span><br><span class="line">        &#123;  </span><br><span class="line">            st.push(p);  </span><br><span class="line">            p&#x3D;p-&gt;left;  </span><br><span class="line">        &#125;  </span><br><span class="line">        p&#x3D;st.top(); &#x2F;&#x2F;获取栈顶元素  </span><br><span class="line">        if( !p-&gt;right || p-&gt;right &#x3D;&#x3D;pre)&#x2F;&#x2F;如果p没有右孩子或者其右孩子刚刚被访问过.小窍门if (!p)表示如果p为空  </span><br><span class="line">        &#123;  </span><br><span class="line">            st.pop();  </span><br><span class="line">            cout&lt;&lt;p-&gt;value&lt;&lt;&#39; &#39;;  </span><br><span class="line">            pre&#x3D;p;      &#x2F;&#x2F;最近一次访问的节点是p  </span><br><span class="line">            p&#x3D;NULL;     &#x2F;&#x2F;使下一次循环不再执行p节点以下的压栈操作  </span><br><span class="line">        &#125;  </span><br><span class="line">        else  </span><br><span class="line">            p&#x3D;p-&gt;right;  </span><br><span class="line">    &#125;  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>5.怎样从根结点开始逐层打印二叉树结点数据.<br>广度优先原则,需要用到队列,当访问一个当前节点CurrentNode的时候,将该结点出队,同时将该CurrentNode的左右子结点入队,重复这个操作,直至队列为空.步骤:1初始化队列.2重复出队入队操作直至队列为空.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;从顶部开始逐层打印二叉树结点数据,即广度遍历二叉树，需要用到队列</span><br><span class="line">void printHori(node* root)</span><br><span class="line">&#123;</span><br><span class="line">	if(!root) return ;</span><br><span class="line">	queue&lt;node*&gt; Q;</span><br><span class="line">	Q.push(root);</span><br><span class="line">	while(!Q.empty())</span><br><span class="line">	&#123;</span><br><span class="line">		node* Front&#x3D;Q.front();</span><br><span class="line">		Q.pop();</span><br><span class="line">		cout&lt;&lt;Front-&gt;value&lt;&lt;&#39; &#39;;</span><br><span class="line">		if(Front-&gt;left)</span><br><span class="line">			Q.push(Front-&gt;left);</span><br><span class="line">		if(Front-&gt;right)</span><br><span class="line">			Q.push(Front-&gt;right);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>6.获得树的深度<br>树的深度=max(左子树深度,右子树深度)+1</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;获得树的深度</span><br><span class="line">int GetTreeDepth(node* root)</span><br><span class="line">&#123;</span><br><span class="line">	if(!root)</span><br><span class="line">		return 0;</span><br><span class="line">	int left&#x3D;GetTreeDepth(root-&gt;left);</span><br><span class="line">	int right&#x3D;GetTreeDepth(root-&gt;right);</span><br><span class="line">	return 1+(left &gt; right? left:right);&#x2F;&#x2F;max(左子树,右子树)+1为整棵树高度</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>7.如何判断一棵二叉树是否是平衡二叉树.<br>方法1:最直接的办法:获得左子树深度,获得左右子树深度,判断二者是否相差在1以内,如果是,则说明当前根结点root是平衡.否则可以判断false.继续用同样的办法判断root的左右子树是否也平衡.现在分析一下这种办法的效率:GetTreeDepth()函数类似于树的后序遍历,T(n)=2<em>T(n/2)+1,由主定理:T(n)=o(n).即,要找到树的深度需要将每个结点全扫描一遍.同样求isTreeBalance(left) 和 isTreeBalance(right)也需要将左右子树重复扫描一遍.这样重重复复扫描树的方式效率是多少?T(N)=2</em>T(N/2)+N,即T(n)=nlgn.</p>
<p>方法2:为了克服多次扫描节点方法的缺陷,我们试图用空间换时间的做法,或者是自底向上的思维方式.方法的方式是,先求根是否平衡,再求左右子树是否平衡.现在,我可以换一个角度,先求左右子树是否平衡,如果左右子树平衡,再考虑求根结点,否则直接返回false.这种方式需要在左右子树返回根时保存树的深度.即空间换时间.这种方法的复杂度为:T(n)=2*T(n/2)+1.T(n)=n.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;判断树是否平衡</span><br><span class="line">bool isTreeBalance(node* root)</span><br><span class="line">&#123;</span><br><span class="line">	if(!root) </span><br><span class="line">		return true ;</span><br><span class="line">	int left&#x3D;GetTreeDepth(root-&gt;left);</span><br><span class="line">	int right&#x3D;GetTreeDepth(root-&gt;right);</span><br><span class="line">	if((left - right) &gt; 1 || (right-left) &gt; 1) </span><br><span class="line">		return false;</span><br><span class="line">	return isTreeBalance(root-&gt;left) &amp;&amp; isTreeBalance(root-&gt;right);</span><br><span class="line">&#125;</span><br><span class="line">&#x2F;&#x2F;判断树是否平衡</span><br><span class="line">bool isBalanceTree(node* root,int&amp; depth)</span><br><span class="line">&#123;	</span><br><span class="line">	if(!root)</span><br><span class="line">	&#123;</span><br><span class="line">		depth&#x3D;0;</span><br><span class="line">		return true;</span><br><span class="line">	&#125;</span><br><span class="line">	int left,right;</span><br><span class="line">	if(isBalanceTree(root-&gt;left,left) &amp;&amp; isBalanceTree(root-&gt;right,right))</span><br><span class="line">	&#123;</span><br><span class="line">		if(left-right &lt;&#x3D; 1 &amp;&amp; right-left &lt;&#x3D; 1)</span><br><span class="line">		&#123;</span><br><span class="line">			depth&#x3D;1+ (left &gt; right ? left:right);</span><br><span class="line">			return true;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	return false;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<p>拓展：判断一棵树是否平衡<br><a href="http://hawstein.com/posts/4.1.html" target="_blank" rel="noopener">http://hawstein.com/posts/4.1.html</a><br>实现一个函数检查一棵树是否平衡。对于这个问题而言， 平衡指的是这棵树任意两个叶子结点到根结点的距离之差不大于1。<br>对于这道题，要审清题意。它并不是让你判断一棵树是否为平衡二叉树。 </p>
<p>平衡二叉树的定义为：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。 </p>
<p>而本题的平衡指的是这棵树任意两个叶子结点到根结点的距离之差不大于1。 这两个概念是不一样的。例如下图，</p>
<p>它是一棵平衡二叉树，但不满足本题的平衡条件。 (叶子结点f和l到根结点的距离之差等于2，不满足题目条件)</p>
<p>对于本题，只需要求出离根结点最近和最远的叶子结点， 然后看它们到根结点的距离之差是否大于1即可。</p>
<p>假设只考虑二叉树，我们可以通过遍历一遍二叉树求出每个叶子结点到根结点的距离。 使用中序遍历，依次求出从左到右的叶子结点到根结点的距离，递归实现。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;*判断树是否平衡，并不是判断是否是平衡二叉树*&#x2F;</span><br><span class="line">int Max&#x3D;INT_MIN,Min&#x3D;INT_MAX,curLen&#x3D;0;</span><br><span class="line">void FindDepth(node* root)</span><br><span class="line">&#123;</span><br><span class="line">	if( root&#x3D;&#x3D;NULL) </span><br><span class="line">	&#123;</span><br><span class="line">		return ;</span><br><span class="line">	&#125;</span><br><span class="line">	++curLen;</span><br><span class="line">	FindDepth(root-&gt;left);</span><br><span class="line">	if( root-&gt;left &#x3D;&#x3D;NULL &amp;&amp; root-&gt;right &#x3D;&#x3D;NULL)</span><br><span class="line">	&#123;</span><br><span class="line">		if( curLen &gt; Max )</span><br><span class="line">			Max&#x3D;curLen;</span><br><span class="line">		else if( curLen &lt; Min )</span><br><span class="line">			Min&#x3D;curLen;</span><br><span class="line">	&#125;</span><br><span class="line">	FindDepth(root-&gt;right);</span><br><span class="line">	--curLen;</span><br><span class="line">&#125;</span><br><span class="line">bool isBalance(node* root)</span><br><span class="line">&#123;</span><br><span class="line">	FindDepth(root);</span><br><span class="line">	return ((Max-Min)&lt;&#x3D;1);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>8.求二叉树的最低公共祖先LCA<br>性质:如果两条链有公共祖先,那么公共祖先往上的结点都重合.因为如果x=x’,那么x-&gt;next=x’-&gt;next必然成立.</p>
<p>可能性一:若是二叉搜索树.</p>
<p>1如果x,y小于root,则在左边找</p>
<p>2如果x,y大于root,则在右边找</p>
<p>3如果x,y在root之间,则root就是LCA</p>
<p>可能性二:不是二叉搜索树,甚至不是二叉树,但是,每个一节点都有parent指针</p>
<p>那么解法有2:</p>
<p>1:空间换时间:从x,y到root的链表可以保存在栈中,找出最后一个相同结点即可.</p>
<p>2.不用空间换时间,多重扫描法,x,y到root两条链路可能一长一短,相差为n个结点,那么长链表先前移n步,然后,二者同步前移,找到第一个相同结点即可.(树不含环,这种办法有效.)</p>
<p>可能性三:这是一棵只有left和right的平凡二叉树.</p>
<p>那么需要辅助空间,空间换时间法,先调用16.中的GetNodePath()获得两条从root-&gt;x和root-&gt;y的链表路径.然后比较两条链表,找到最后一个相同的结点即可.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;若是二叉搜索树,返回x和y的公共最低祖先LCA</span><br><span class="line">node* LowestCommonAncestor1(node* root,node* x,node* y)</span><br><span class="line">&#123;</span><br><span class="line">	if(!root || !x || !y) return NULL;</span><br><span class="line">	if(x-&gt;value &lt; root-&gt;value &amp;&amp; y-&gt;value &lt; root-&gt;value)</span><br><span class="line">		return LowestCommonAncestor1(root-&gt;left,x,y);</span><br><span class="line">	else if(x-&gt;value &gt; root-&gt;value &amp;&amp; y-&gt;value &gt; root-&gt;value)</span><br><span class="line">		return LowestCommonAncestor1(root-&gt;right,x,y);</span><br><span class="line">	else </span><br><span class="line">		return root;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;若不是搜索二叉树,但是,每个结点都有父结点,空间换时间法,否则需要重重复复地扫描路径</span><br><span class="line">node* LowestCommonAncestor2(node* x,node* y)</span><br><span class="line">&#123;</span><br><span class="line">	stack&lt;node*&gt; st1,st2;</span><br><span class="line">	while(x)</span><br><span class="line">	&#123;</span><br><span class="line">		st1.push(x);</span><br><span class="line">		x&#x3D;x-&gt;p;</span><br><span class="line">	&#125;</span><br><span class="line">	while(y)</span><br><span class="line">	&#123;</span><br><span class="line">		st2.push(y);</span><br><span class="line">		y&#x3D;y-&gt;p;</span><br><span class="line">	&#125;</span><br><span class="line">	node* pLCA&#x3D;NULL;</span><br><span class="line">	while(!st1.empty() &amp;&amp; !st2.empty() &amp;&amp; st1.top()&#x3D;&#x3D;st2.top())</span><br><span class="line">	&#123;</span><br><span class="line">		pLCA&#x3D;st1.top();</span><br><span class="line">		st1.pop();</span><br><span class="line">		st2.pop();</span><br><span class="line">	&#125;	</span><br><span class="line">	return pLCA;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;不用空间换时间法</span><br><span class="line">int GetListLength(node* x)</span><br><span class="line">&#123;</span><br><span class="line">	int Count&#x3D;0;</span><br><span class="line">	while(x)</span><br><span class="line">	&#123;</span><br><span class="line">		++Count;</span><br><span class="line">		x&#x3D;x-&gt;p;</span><br><span class="line">	&#125;</span><br><span class="line">	return Count;</span><br><span class="line">&#125;</span><br><span class="line">int Myabs(int val)</span><br><span class="line">&#123;</span><br><span class="line">	return val &gt; 0 ? val : -val;</span><br><span class="line">&#125;</span><br><span class="line">node* LowestCommonAncestor3(node* x,node* y)</span><br><span class="line">&#123;</span><br><span class="line">	int LengthX&#x3D;GetListLength(x);</span><br><span class="line">	int LengthY&#x3D;GetListLength(y);</span><br><span class="line">	node* pLong&#x3D;x,*pShort&#x3D;y;</span><br><span class="line">	if(LengthX &lt; LengthY)</span><br><span class="line">	&#123;</span><br><span class="line">		pLong&#x3D;y;</span><br><span class="line">		pShort&#x3D;x;</span><br><span class="line">	&#125;</span><br><span class="line">	for(int i&#x3D;0;i&lt;Myabs(LengthX-LengthY);++i)</span><br><span class="line">		pLong&#x3D;pLong-&gt;p;</span><br><span class="line">	while( pLong &amp;&amp; pShort &amp;&amp; pLong !&#x3D;pShort)</span><br><span class="line">	&#123;</span><br><span class="line">		pLong&#x3D;pLong-&gt;p;</span><br><span class="line">		pShort&#x3D;pShort-&gt;p;</span><br><span class="line">	&#125;</span><br><span class="line">	if(pLong &#x3D;&#x3D; pShort)</span><br><span class="line">		return pLong;</span><br><span class="line">	return NULL;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;既不是二叉搜索树,也不没有parent指针,只是一棵平凡的二叉树</span><br><span class="line">bool GetNodePath(node* root, node* pNode, list&lt;node*&gt;&amp; path);</span><br><span class="line">node* LowestCommonAncestor4(node* root,node* x,node* y)</span><br><span class="line">&#123;</span><br><span class="line">	list&lt;node*&gt; path1;</span><br><span class="line">	list&lt;node*&gt; path2;</span><br><span class="line">	GetNodePath(root,x,path1);</span><br><span class="line">	GetNodePath(root,y,path2);</span><br><span class="line">	node* pLCA&#x3D;NULL;</span><br><span class="line">	list&lt;node*&gt;::const_iterator it1&#x3D;path1.begin();</span><br><span class="line">	list&lt;node*&gt;::const_iterator it2&#x3D;path2.begin();</span><br><span class="line">	while(it1 !&#x3D; path1.end() &amp;&amp; it2 !&#x3D; path2.end() &amp;&amp; *it1 &#x3D;&#x3D; * it2)</span><br><span class="line">	&#123;</span><br><span class="line">		pLCA&#x3D;*it1;</span><br><span class="line">		++it1;</span><br><span class="line">		++it2;</span><br><span class="line">	&#125;	</span><br><span class="line">	return pLCA;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>9.在二叉树中找出和为某一值的所有路径<br>要求所有路径,路径即root到某一结点的结点之集合.这是一个深度优先原则的搜索.我们很容易想到先序遍历.</p>
<p>为了跟踪路径和,我们需要一个额外的辅助栈来跟踪递归调用栈的操作过程.</p>
<p>在进入到下一个调用FindPath(left)和FindPath(right)时,递归栈会将root压入栈,因此我们也模仿进栈.当FindPath(left)和FindPath(right)返回,FindPath(root)运行周期到之后,局部函数变量root会被析造,root会从递归栈中弹出,因此,我们也从辅助栈中弹出root,只需要在中间加上判断条件,将满足条件的结果输出即可.改成迭代版也很简单.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line">void FindPath(node* root,int expectedSum,vector&lt;int&gt;&amp; Path,int currentSum);&#x2F;&#x2F;先序遍历改装版</span><br><span class="line">void FindPath(node* root,int expectedSum)</span><br><span class="line">&#123;</span><br><span class="line">	int currentSum&#x3D;0;</span><br><span class="line">	vector&lt;int&gt; Path;</span><br><span class="line">	FindPath(root,expectedSum,Path,currentSum);</span><br><span class="line">&#125;</span><br><span class="line">void FindPath(node* root,int expectedSum,vector&lt;int&gt;&amp; Path,int currentSum)&#x2F;&#x2F;先序遍历改装版</span><br><span class="line">&#123;</span><br><span class="line">	if(!root)</span><br><span class="line">		return ;</span><br><span class="line">	&#x2F;&#x2F;访问根结点,同时将root-&gt;value加入辅助栈</span><br><span class="line">	currentSum +&#x3D; root-&gt;value;</span><br><span class="line">	Path.push_back(root-&gt;value);</span><br><span class="line">	if(root-&gt;left&#x3D;&#x3D;NULL &amp;&amp; root-&gt;right &#x3D;&#x3D;NULL &amp;&amp; currentSum &#x3D;&#x3D; expectedSum)</span><br><span class="line">	&#123;</span><br><span class="line">		for(vector&lt;int&gt;::size_type i&#x3D;0; i &lt; Path.size(); ++i)</span><br><span class="line">			cout&lt;&lt;Path[i]&lt;&lt;&#39; &#39;;</span><br><span class="line">		cout&lt;&lt;endl;</span><br><span class="line">	&#125;</span><br><span class="line">	FindPath(root-&gt;left,expectedSum,Path,currentSum);</span><br><span class="line">	FindPath(root-&gt;right,expectedSum,Path,currentSum);</span><br><span class="line">	&#x2F;&#x2F;递归栈中,此时返回时,会将父结点销毁,因为,局部函数生命周期已经到了.</span><br><span class="line">	&#x2F;&#x2F;所以辅助栈也需要和递归栈同步,将栈顶元素弹栈,同时当前路径减去栈顶元素</span><br><span class="line">	Path.pop_back();</span><br><span class="line">	currentSum-&#x3D;root-&gt;value;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>10.编写一个程序，把一个有序整数数组放到二叉树中<br>这道题做法非常多,单纯是这么要求比较奇怪,因此,我选择广度优先插入,利用队列实现,其实插成一个链表,或者随便插入不知道可不可以?没有其它要求真不知道怎么弄.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line">node* HorizInsert(node* root,node* z)</span><br><span class="line">&#123;</span><br><span class="line">    if(!root)</span><br><span class="line">    &#123;</span><br><span class="line">        root&#x3D;z;</span><br><span class="line">        return root;</span><br><span class="line">    &#125;</span><br><span class="line">    queue&lt;node*&gt; q;</span><br><span class="line">    q.push(root);</span><br><span class="line">    while(!q.empty())</span><br><span class="line">    &#123;</span><br><span class="line">        node* Front&#x3D;q.front();</span><br><span class="line">        q.pop();</span><br><span class="line">        if(Front-&gt;left&#x3D;&#x3D;NULL)</span><br><span class="line">        &#123;</span><br><span class="line">            Front-&gt;left&#x3D;z;</span><br><span class="line">            return root;</span><br><span class="line">        &#125;</span><br><span class="line">        if(Front-&gt;right&#x3D;&#x3D;NULL)</span><br><span class="line">        &#123;</span><br><span class="line">            Front-&gt;right&#x3D;z;</span><br><span class="line">            return root;</span><br><span class="line">        &#125;</span><br><span class="line">        if(Front-&gt;left)</span><br><span class="line">            q.push(Front-&gt;left);</span><br><span class="line">        if(Front-&gt;right)</span><br><span class="line">            q.push(Front-&gt;right);</span><br><span class="line">    &#125;</span><br><span class="line">    return root;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>11.判断整数序列是不是二叉搜索树的后序遍历结果<br>典型的递归思维,后序遍历,根在最后,因此用根将二叉搜索树可以分成左右子树,再递归处理左右子树即可.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;判断整数序列是不是二叉搜索树的后序遍历结果  </span><br><span class="line">bool isPostTreeWalk(int* Last,int len)</span><br><span class="line">&#123;</span><br><span class="line">	if( !Last || len &lt;&#x3D; 0)</span><br><span class="line">		return false;</span><br><span class="line">	int root&#x3D;Last[len-1];</span><br><span class="line">	int i&#x3D;0;</span><br><span class="line">	while(i &lt; len-1 &amp;&amp; Last[i] &lt; root)&#x2F;&#x2F;寻找左子树划分点</span><br><span class="line">		++i;</span><br><span class="line">	for(int j&#x3D;i ; j &lt; len-1 ; ++j)</span><br><span class="line">	&#123;</span><br><span class="line">		if(Last[j] &lt; root)&#x2F;&#x2F;如果右子树中存在node&lt;root,则无法构成后序结果</span><br><span class="line">			return false;</span><br><span class="line">	&#125;</span><br><span class="line">	bool isLastTree&#x3D;true;</span><br><span class="line">	if(i &gt; 0) &#x2F;&#x2F;判断左边是不是后序树</span><br><span class="line">		isLastTree&#x3D;isPostTreeWalk(Last,i);</span><br><span class="line">	&#x2F;&#x2F;如果左边是后序树，继续判断右边，如果左边已经不是，则右边已经无需判断</span><br><span class="line">	if(isLastTree &amp;&amp; i &lt; len-1 )</span><br><span class="line">		isLastTree&#x3D;isPostTreeWalk(Last+i,len-i-1);</span><br><span class="line">	return isLastTree ;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>12.求二叉树的镜像<br>画出一个特例,我们发现只需要交换每个结点的左右指针(注意:不是数值)即可.因此在先序遍历的时候换指针即可,没有顺序要求.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;求二叉树的镜像  </span><br><span class="line">void MirrorRotate(node* root)</span><br><span class="line">&#123;</span><br><span class="line">	if(!root) return ;</span><br><span class="line">	swap(root-&gt;left,root-&gt;right);</span><br><span class="line">	MirrorRotate(root-&gt;right);</span><br><span class="line">	MirrorRotate(root-&gt;left);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>13.一棵排序二叉树（即二叉搜索树BST），令 f=(最大值+最小值)/2，设计一个算法，找出距离f值最近、大于f值的结点。复杂度应尽可能低。<br>BST中最大值是最右边的值,最小值是最左边的值,这样就容易求出f,再求f的父指针或者右指针都可以?(我是这么认为的).这里求父指针.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;找出距离f值最近、大于f值的结点。</span><br><span class="line">node* FinClearF(node* root)</span><br><span class="line">&#123;</span><br><span class="line">	if(!root) return NULL;</span><br><span class="line">	node* max,*min;</span><br><span class="line">	max&#x3D;min&#x3D;root;</span><br><span class="line">	while(min-&gt;left)</span><br><span class="line">		min&#x3D;min-&gt;left;</span><br><span class="line">	while(max-&gt;right)</span><br><span class="line">		max&#x3D;max-&gt;right;</span><br><span class="line">	int F&#x3D;(min-&gt;value + max-&gt;value) &gt;&gt; 1 ;</span><br><span class="line">	while(1)</span><br><span class="line">	&#123;</span><br><span class="line">		if(root-&gt;value &lt;&#x3D; F)</span><br><span class="line">			root&#x3D;root-&gt;right;</span><br><span class="line">		else</span><br><span class="line">		&#123;</span><br><span class="line">			return root;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<p>14.把二叉搜索树转变成排序的双向链表<br>其实就是中序遍历的迭代版本,只是将中间的访问结点代码换成了调整指针.这种办法返回的是链表的最后一个指针LastVist,因为是双链表,这也可以接受.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;迭代法</span><br><span class="line">node* iTreeToList(node* root)</span><br><span class="line">&#123;</span><br><span class="line">	node* p&#x3D;root;</span><br><span class="line">	stack&lt;node*&gt; st;</span><br><span class="line">	node* LastVist&#x3D;NULL;</span><br><span class="line">	while(p || !st.empty())</span><br><span class="line">	&#123;</span><br><span class="line">		while(p)</span><br><span class="line">		&#123;</span><br><span class="line">			st.push(p);</span><br><span class="line">			p&#x3D;p-&gt;left;</span><br><span class="line">		&#125;</span><br><span class="line">		p&#x3D;st.top();</span><br><span class="line">		st.pop();</span><br><span class="line">		&#x2F;&#x2F;cout&lt;&lt;p-&gt;value&lt;&lt;&#39; &#39;;</span><br><span class="line">		if(LastVist)</span><br><span class="line">		&#123;</span><br><span class="line">			LastVist-&gt;right&#x3D;p;</span><br><span class="line">			p-&gt;left&#x3D;LastVist;</span><br><span class="line">		&#125;</span><br><span class="line">		LastVist&#x3D;p;</span><br><span class="line">		p&#x3D;p-&gt;right;</span><br><span class="line">	&#125;</span><br><span class="line">	return LastVist;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>15.打印二叉树中的所有路径.<br>和前边的思路类似,用辅助栈记录递归栈的运行过程,先序遍历(深搜)的过程中,遇到叶子结点(!left &amp;&amp; !right的结点)就输出辅助栈的内容.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;输出二叉树的所有路径</span><br><span class="line">void OutputTreePath(node* root,list&lt;node*&gt;&amp; path)</span><br><span class="line">&#123;</span><br><span class="line">	if(!root) return ; </span><br><span class="line">	path.push_back(root);</span><br><span class="line">	if(!root-&gt;left &amp;&amp; !root-&gt;right)</span><br><span class="line">	&#123;</span><br><span class="line">		for(list&lt;node*&gt;::const_iterator it&#x3D;path.begin();it !&#x3D;path.end();++it)</span><br><span class="line">			cout&lt;&lt;(*it)-&gt;value&lt;&lt;&#39; &#39;;</span><br><span class="line">		cout&lt;&lt;endl;</span><br><span class="line">	&#125;</span><br><span class="line">	OutputTreePath(root-&gt;left,path);</span><br><span class="line">	OutputTreePath(root-&gt;right,path);</span><br><span class="line">	&#x2F;&#x2F;运行到这里的时候,函数生命周期到,在返回上一层时</span><br><span class="line">	&#x2F;&#x2F;局部函数会析构root(当前根结点),对应地,也应该将root从path中的值弹出</span><br><span class="line">	path.pop_back();</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>16.求二叉树中从根到某一结点的一条路径.<br>思路一如既往还是利用辅助栈来追踪递归调用栈的运行过程,只是过程有所区别,将结点入栈,如果在结点的左边能找到一条路径,那么不需要和递归栈同步(即弹栈),直接返回true,如果左边没找到这样的一条路径,再到右边找,如果找到了,返回true.如果左右都找不到存在一条这样的路径,则说明在这个结点上不可能存在这样的路径,需要在辅助栈中弹出这个结点.再遍历其它结点.实质上也是先序遍历的改装版.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;获得二叉树中从根到某一结点的一条路径</span><br><span class="line">bool GetNodePath(node* root, node* pNode, list&lt;node*&gt;&amp; path)</span><br><span class="line">&#123;</span><br><span class="line">	if(root &#x3D;&#x3D; pNode)&#x2F;&#x2F;如果root&#x3D;&#x3D;nNode,Done</span><br><span class="line">	&#123;</span><br><span class="line">		path.push_back(pNode);</span><br><span class="line">		return true;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	path.push_back(root);&#x2F;&#x2F;1用root实始化容器</span><br><span class="line">	 </span><br><span class="line">	bool isFound &#x3D; false;</span><br><span class="line">	if(root-&gt;left)</span><br><span class="line">		isFound &#x3D; GetNodePath(root-&gt;left, pNode, path);</span><br><span class="line">	if(!isFound &amp;&amp; root-&gt;right)</span><br><span class="line">		isFound &#x3D; GetNodePath(root-&gt;right, pNode, path);</span><br><span class="line">	 </span><br><span class="line">	if(!isFound)&#x2F;&#x2F;如果1中的左右子树都没找到，说明在这个root上不存在这样的路径，需要将root弹出</span><br><span class="line">		path.pop_back();</span><br><span class="line">	 </span><br><span class="line">	return isFound;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>17判断B子树是否是A子树的子结构<br>这个似乎是有问题的,暂时还没有找到好的解决方案.求大神相助.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;判断B是否是A的子结构</span><br><span class="line">bool isAcontainB(node* rootA,node* rootB)</span><br><span class="line">&#123;</span><br><span class="line">	if(!rootB)</span><br><span class="line">		return true;</span><br><span class="line">	if(!rootA)</span><br><span class="line">		return false;</span><br><span class="line">	if(rootA-&gt;value &#x3D;&#x3D; rootB-&gt;value)</span><br><span class="line">		return isAcontainB(rootA-&gt;left,rootB-&gt;left) &amp;&amp; isAcontainB(rootA-&gt;right,rootB-&gt;right);</span><br><span class="line">	return isAcontainB(rootA-&gt;left,rootB) || isAcontainB(rootA-&gt;right,rootB);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>18.利用先序和中序结果重建二叉树<br>在先序中找到根,利用根在中序中找到划分位置,再从划分位置把先序切成两部分,再依次递归即可.</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F;利用先序和中序结果重建二叉树</span><br><span class="line">node* RebuildTree(int* Prec,int * Post,int n)</span><br><span class="line">&#123;</span><br><span class="line">	if(!Prec || !Post || n&lt;1) </span><br><span class="line">		return NULL;</span><br><span class="line">	node* root&#x3D;new node(Prec[0]);</span><br><span class="line">	int i;</span><br><span class="line">	for(i&#x3D;0 ; i&lt;n &amp;&amp; Post[i] !&#x3D;Prec[0] ; ++i );</span><br><span class="line">	</span><br><span class="line"></span><br><span class="line">	root-&gt;left&#x3D;RebuildTree(Prec+1,Post,i);</span><br><span class="line">	</span><br><span class="line">	root-&gt;right&#x3D;RebuildTree(Prec+1+i,Post+1+i,n-i-1);</span><br><span class="line">	return root;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<p>19.求二叉树中叶子结点的个数</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">void CountLeaves(node* root,int&amp; Count)</span><br><span class="line">&#123;</span><br><span class="line">	if(!root ) return ;</span><br><span class="line">	if(!root-&gt;left &amp;&amp; !root-&gt;right)</span><br><span class="line">		++Count;</span><br><span class="line">	CountLeaves(root-&gt;left,Count);</span><br><span class="line">	CountLeaves(root-&gt;right,Count);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


<p>20.求二叉树中节点的最大距离。<br>如果我们把二叉树看成一个图，父子节点之间的连线是双向的，我们定义距离为两个节点之间边的个数。（来自编程之美）</p>
<p>特点：相距最远的两个节点，一定是两个叶子节点，或者一个结点到它的根节点。（为什么？）因为如果当前结点不是叶子结点，即它还有子结点，那么它的子结点到另一个端点的距离肯定可以达到更远。如果是根结点，那么根结点只可能有一条支路。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F; 数据结构定义</span><br><span class="line">struct NODE</span><br><span class="line">&#123;</span><br><span class="line">     NODE* pLeft;        	&#x2F;&#x2F; 左子树</span><br><span class="line">     NODE* pRight;      	&#x2F;&#x2F; 右子树</span><br><span class="line">     int nMaxLeft;      	&#x2F;&#x2F; 左子树中的最长距离</span><br><span class="line">     int nMaxRight;     	&#x2F;&#x2F; 右子树中的最长距离</span><br><span class="line">     char chValue;    	&#x2F;&#x2F; 该节点的值</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line">int nMaxLen &#x3D; 0;</span><br><span class="line"></span><br><span class="line">&#x2F;&#x2F; 寻找树中最长的两段距离</span><br><span class="line">void FindMaxLen(NODE* pRoot)</span><br><span class="line">&#123;</span><br><span class="line">     &#x2F;&#x2F; 遍历到叶子节点，返回</span><br><span class="line">     if(pRoot &#x3D;&#x3D; NULL)</span><br><span class="line">     &#123;</span><br><span class="line">          return;</span><br><span class="line">     &#125;</span><br><span class="line"></span><br><span class="line">     &#x2F;&#x2F; 如果左子树为空，那么该节点的左边最长距离为0</span><br><span class="line">     if(pRoot -&gt; pLeft &#x3D;&#x3D; NULL)</span><br><span class="line">     &#123;</span><br><span class="line">          pRoot -&gt; nMaxLeft &#x3D; 0; </span><br><span class="line">     &#125;</span><br><span class="line">     </span><br><span class="line">     &#x2F;&#x2F; 如果右子树为空，那么该节点的右边最长距离为0</span><br><span class="line">     if(pRoot -&gt; pRight &#x3D;&#x3D; NULL)</span><br><span class="line">     &#123;</span><br><span class="line">          pRoot -&gt; nMaxRight &#x3D; 0;</span><br><span class="line">     &#125;</span><br><span class="line">     </span><br><span class="line">     &#x2F;&#x2F; 如果左子树不为空，递归寻找左子树最长距离</span><br><span class="line">     if(pRoot -&gt; pLeft !&#x3D; NULL)</span><br><span class="line">     &#123;</span><br><span class="line">          FindMaxLen(pRoot -&gt; pLeft);</span><br><span class="line">     &#125;</span><br><span class="line">     </span><br><span class="line">     &#x2F;&#x2F; 如果右子树不为空，递归寻找右子树最长距离</span><br><span class="line">     if(pRoot -&gt; pRight !&#x3D; NULL)</span><br><span class="line">     &#123;</span><br><span class="line">          FindMaxLen(pRoot -&gt; pRight);</span><br><span class="line">     &#125;</span><br><span class="line">     </span><br><span class="line">     &#x2F;&#x2F; 计算左子树最长节点距离</span><br><span class="line">     if(pRoot -&gt; pLeft !&#x3D; NULL)</span><br><span class="line">     &#123;</span><br><span class="line">          int nTempMax &#x3D; 0;</span><br><span class="line">          if(pRoot -&gt; pLeft -&gt; nMaxLeft &gt; pRoot -&gt; pLeft -&gt; nMaxRight)</span><br><span class="line">          &#123;</span><br><span class="line">               nTempMax &#x3D; pRoot -&gt; pLeft -&gt; nMaxLeft;</span><br><span class="line">          &#125;</span><br><span class="line">          else</span><br><span class="line">          &#123;</span><br><span class="line">               nTempMax &#x3D; pRoot -&gt; pLeft -&gt; nMaxRight;</span><br><span class="line">          &#125;</span><br><span class="line">          pRoot -&gt; nMaxLeft &#x3D; nTempMax + 1;</span><br><span class="line">     &#125;</span><br><span class="line">     </span><br><span class="line">     &#x2F;&#x2F; 计算右子树最长节点距离</span><br><span class="line">     if(pRoot -&gt; pRight !&#x3D; NULL)</span><br><span class="line">     &#123;</span><br><span class="line">          int nTempMax &#x3D; 0;</span><br><span class="line">          if(pRoot -&gt; pRight -&gt; nMaxLeft &gt; pRoot -&gt; pRight -&gt; nMaxRight)</span><br><span class="line">          &#123;</span><br><span class="line">               nTempMax &#x3D; pRoot -&gt; pRight -&gt; nMaxLeft;</span><br><span class="line">          &#125;</span><br><span class="line">          else</span><br><span class="line">          &#123;</span><br><span class="line">               nTempMax &#x3D; pRoot -&gt; pRight -&gt; nMaxRight;</span><br><span class="line">          &#125;</span><br><span class="line">          pRoot -&gt; nMaxRight &#x3D; nTempMax + 1;</span><br><span class="line">     &#125;</span><br><span class="line">     </span><br><span class="line">     &#x2F;&#x2F; 更新最长距离</span><br><span class="line">     if(pRoot -&gt; nMaxLeft + pRoot -&gt; nMaxRight &gt; nMaxLen)</span><br><span class="line">     &#123;</span><br><span class="line">          nMaxLen &#x3D; pRoot -&gt; nMaxLeft + pRoot -&gt; nMaxRight;</span><br><span class="line">     &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>递归总结：</p>
<p>1.先弄清楚递归的顺序。在递归的过程中，往往需要假设后续的调用已经完成，在此基础之上，才实现递归的逻辑。</p>
<p>2.分析清楚递归体的逻辑，然后写出来。</p>
<p>3.考虑清楚递归退出的边界条件。即在哪些地方写上return.</p>
<p>21.打印二叉树中某层的结点。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line">&#x2F;&#x2F; 输出以root为根节点中的第level层中的所有节点（从左到右）, 成功返回1，</span><br><span class="line">&#x2F;&#x2F; 失败则返回0</span><br><span class="line">&#x2F;&#x2F; @param</span><br><span class="line">&#x2F;&#x2F; root 为二叉树的根节点 </span><br><span class="line">&#x2F;&#x2F; level为层次数，其中根节点为第0层</span><br><span class="line">int PrintNodeAtLevel(Node* root, int level)</span><br><span class="line">&#123;</span><br><span class="line">     if(!root || level &lt; 0)</span><br><span class="line">          return 0;</span><br><span class="line">     if(level &#x3D;&#x3D; 0)</span><br><span class="line">     &#123;</span><br><span class="line">          cout &lt;&lt; root -&gt; data &lt;&lt; &quot; &quot;;</span><br><span class="line">          return 1;</span><br><span class="line">     &#125;</span><br><span class="line">     return PrintNodeAtLevel(node -&gt; lChild, level - 1) + PrintNodeAtLevel</span><br><span class="line">       (node -&gt; rChild, level - 1);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>22.判断两棵二叉树是否相等</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line">bool IsEqual(node *root1, node *root2)</span><br><span class="line">&#123;</span><br><span class="line">	if (root1 !&#x3D; NULL &amp;&amp; root2 !&#x3D; NULL)</span><br><span class="line">	&#123;</span><br><span class="line">		if (root1-&gt;data !&#x3D; root2-&gt;data)</span><br><span class="line">		&#123;</span><br><span class="line">			return false;</span><br><span class="line">		&#125;</span><br><span class="line">		if (IsEqual(root1-&gt;left, root2-&gt;left) &amp;&amp; IsEqual(root1-&gt;right, root2-&gt;right))</span><br><span class="line">		&#123;</span><br><span class="line">			return true;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	else</span><br><span class="line">	&#123;</span><br><span class="line">		if (root1 &#x3D;&#x3D; NULL &amp;&amp; root2 &#x3D;&#x3D; NULL)</span><br><span class="line">		&#123;</span><br><span class="line">			return true;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	return false;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>


          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
  </section>

  
  <nav class="pagination">
    <span class="page-number current">1</span><a class="page-number" href="/page/2/">2</a><a class="extend next" rel="next" href="/page/2/">></a>
  </nav>


          </div>
          


          

        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      

      <section class="site-overview-wrap sidebar-panel sidebar-panel-active">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <p class="site-author-name" itemprop="name">LinRaise</p>
              <p class="site-description motion-element" itemprop="description"></p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">16</span>
                  <span class="site-state-item-name">posts</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">2</span>
                  <span class="site-state-item-name">categories</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">1</span>
                  <span class="site-state-item-name">tags</span>
                </a>
              </div>
            

          </nav>

          

          

          
          

          
          

          

        </div>
      </section>

      

      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; <span itemprop="copyrightYear">2020</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">LinRaise</span>

  
</div>


  <div class="powered-by">Powered by <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a></div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">Theme &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Gemini</a> v5.1.4</div>




        







        
      </div>
    </footer>

    
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
        
      </div>
    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.4"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.4"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.4"></script>



  

  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.4"></script>



  


  




	





  





  












  

  <script type="text/javascript">
    // Popup Window;
    var isfetched = false;
    var isXml = true;
    // Search DB path;
    var search_path = "search.xml";
    if (search_path.length === 0) {
      search_path = "search.xml";
    } else if (/json$/i.test(search_path)) {
      isXml = false;
    }
    var path = "/" + search_path;
    // monitor main search box;

    var onPopupClose = function (e) {
      $('.popup').hide();
      $('#local-search-input').val('');
      $('.search-result-list').remove();
      $('#no-result').remove();
      $(".local-search-pop-overlay").remove();
      $('body').css('overflow', '');
    }

    function proceedsearch() {
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay"></div>')
        .css('overflow', 'hidden');
      $('.search-popup-overlay').click(onPopupClose);
      $('.popup').toggle();
      var $localSearchInput = $('#local-search-input');
      $localSearchInput.attr("autocapitalize", "none");
      $localSearchInput.attr("autocorrect", "off");
      $localSearchInput.focus();
    }

    // search function;
    var searchFunc = function(path, search_id, content_id) {
      'use strict';

      // start loading animation
      $("body")
        .append('<div class="search-popup-overlay local-search-pop-overlay">' +
          '<div id="search-loading-icon">' +
          '<i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>' +
          '</div>' +
          '</div>')
        .css('overflow', 'hidden');
      $("#search-loading-icon").css('margin', '20% auto 0 auto').css('text-align', 'center');

      $.ajax({
        url: path,
        dataType: isXml ? "xml" : "json",
        async: true,
        success: function(res) {
          // get the contents from search data
          isfetched = true;
          $('.popup').detach().appendTo('.header-inner');
          var datas = isXml ? $("entry", res).map(function() {
            return {
              title: $("title", this).text(),
              content: $("content",this).text(),
              url: $("url" , this).text()
            };
          }).get() : res;
          var input = document.getElementById(search_id);
          var resultContent = document.getElementById(content_id);
          var inputEventFunction = function() {
            var searchText = input.value.trim().toLowerCase();
            var keywords = searchText.split(/[\s\-]+/);
            if (keywords.length > 1) {
              keywords.push(searchText);
            }
            var resultItems = [];
            if (searchText.length > 0) {
              // perform local searching
              datas.forEach(function(data) {
                var isMatch = false;
                var hitCount = 0;
                var searchTextCount = 0;
                var title = data.title.trim();
                var titleInLowerCase = title.toLowerCase();
                var content = data.content.trim().replace(/<[^>]+>/g,"");
                var contentInLowerCase = content.toLowerCase();
                var articleUrl = decodeURIComponent(data.url);
                var indexOfTitle = [];
                var indexOfContent = [];
                // only match articles with not empty titles
                if(title != '') {
                  keywords.forEach(function(keyword) {
                    function getIndexByWord(word, text, caseSensitive) {
                      var wordLen = word.length;
                      if (wordLen === 0) {
                        return [];
                      }
                      var startPosition = 0, position = [], index = [];
                      if (!caseSensitive) {
                        text = text.toLowerCase();
                        word = word.toLowerCase();
                      }
                      while ((position = text.indexOf(word, startPosition)) > -1) {
                        index.push({position: position, word: word});
                        startPosition = position + wordLen;
                      }
                      return index;
                    }

                    indexOfTitle = indexOfTitle.concat(getIndexByWord(keyword, titleInLowerCase, false));
                    indexOfContent = indexOfContent.concat(getIndexByWord(keyword, contentInLowerCase, false));
                  });
                  if (indexOfTitle.length > 0 || indexOfContent.length > 0) {
                    isMatch = true;
                    hitCount = indexOfTitle.length + indexOfContent.length;
                  }
                }

                // show search results

                if (isMatch) {
                  // sort index by position of keyword

                  [indexOfTitle, indexOfContent].forEach(function (index) {
                    index.sort(function (itemLeft, itemRight) {
                      if (itemRight.position !== itemLeft.position) {
                        return itemRight.position - itemLeft.position;
                      } else {
                        return itemLeft.word.length - itemRight.word.length;
                      }
                    });
                  });

                  // merge hits into slices

                  function mergeIntoSlice(text, start, end, index) {
                    var item = index[index.length - 1];
                    var position = item.position;
                    var word = item.word;
                    var hits = [];
                    var searchTextCountInSlice = 0;
                    while (position + word.length <= end && index.length != 0) {
                      if (word === searchText) {
                        searchTextCountInSlice++;
                      }
                      hits.push({position: position, length: word.length});
                      var wordEnd = position + word.length;

                      // move to next position of hit

                      index.pop();
                      while (index.length != 0) {
                        item = index[index.length - 1];
                        position = item.position;
                        word = item.word;
                        if (wordEnd > position) {
                          index.pop();
                        } else {
                          break;
                        }
                      }
                    }
                    searchTextCount += searchTextCountInSlice;
                    return {
                      hits: hits,
                      start: start,
                      end: end,
                      searchTextCount: searchTextCountInSlice
                    };
                  }

                  var slicesOfTitle = [];
                  if (indexOfTitle.length != 0) {
                    slicesOfTitle.push(mergeIntoSlice(title, 0, title.length, indexOfTitle));
                  }

                  var slicesOfContent = [];
                  while (indexOfContent.length != 0) {
                    var item = indexOfContent[indexOfContent.length - 1];
                    var position = item.position;
                    var word = item.word;
                    // cut out 100 characters
                    var start = position - 20;
                    var end = position + 80;
                    if(start < 0){
                      start = 0;
                    }
                    if (end < position + word.length) {
                      end = position + word.length;
                    }
                    if(end > content.length){
                      end = content.length;
                    }
                    slicesOfContent.push(mergeIntoSlice(content, start, end, indexOfContent));
                  }

                  // sort slices in content by search text's count and hits' count

                  slicesOfContent.sort(function (sliceLeft, sliceRight) {
                    if (sliceLeft.searchTextCount !== sliceRight.searchTextCount) {
                      return sliceRight.searchTextCount - sliceLeft.searchTextCount;
                    } else if (sliceLeft.hits.length !== sliceRight.hits.length) {
                      return sliceRight.hits.length - sliceLeft.hits.length;
                    } else {
                      return sliceLeft.start - sliceRight.start;
                    }
                  });

                  // select top N slices in content

                  var upperBound = parseInt('1');
                  if (upperBound >= 0) {
                    slicesOfContent = slicesOfContent.slice(0, upperBound);
                  }

                  // highlight title and content

                  function highlightKeyword(text, slice) {
                    var result = '';
                    var prevEnd = slice.start;
                    slice.hits.forEach(function (hit) {
                      result += text.substring(prevEnd, hit.position);
                      var end = hit.position + hit.length;
                      result += '<b class="search-keyword">' + text.substring(hit.position, end) + '</b>';
                      prevEnd = end;
                    });
                    result += text.substring(prevEnd, slice.end);
                    return result;
                  }

                  var resultItem = '';

                  if (slicesOfTitle.length != 0) {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + highlightKeyword(title, slicesOfTitle[0]) + "</a>";
                  } else {
                    resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + title + "</a>";
                  }

                  slicesOfContent.forEach(function (slice) {
                    resultItem += "<a href='" + articleUrl + "'>" +
                      "<p class=\"search-result\">" + highlightKeyword(content, slice) +
                      "...</p>" + "</a>";
                  });

                  resultItem += "</li>";
                  resultItems.push({
                    item: resultItem,
                    searchTextCount: searchTextCount,
                    hitCount: hitCount,
                    id: resultItems.length
                  });
                }
              })
            };
            if (keywords.length === 1 && keywords[0] === "") {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-search fa-5x" /></div>'
            } else if (resultItems.length === 0) {
              resultContent.innerHTML = '<div id="no-result"><i class="fa fa-frown-o fa-5x" /></div>'
            } else {
              resultItems.sort(function (resultLeft, resultRight) {
                if (resultLeft.searchTextCount !== resultRight.searchTextCount) {
                  return resultRight.searchTextCount - resultLeft.searchTextCount;
                } else if (resultLeft.hitCount !== resultRight.hitCount) {
                  return resultRight.hitCount - resultLeft.hitCount;
                } else {
                  return resultRight.id - resultLeft.id;
                }
              });
              var searchResultList = '<ul class=\"search-result-list\">';
              resultItems.forEach(function (result) {
                searchResultList += result.item;
              })
              searchResultList += "</ul>";
              resultContent.innerHTML = searchResultList;
            }
          }

          if ('auto' === 'auto') {
            input.addEventListener('input', inputEventFunction);
          } else {
            $('.search-icon').click(inputEventFunction);
            input.addEventListener('keypress', function (event) {
              if (event.keyCode === 13) {
                inputEventFunction();
              }
            });
          }

          // remove loading animation
          $(".local-search-pop-overlay").remove();
          $('body').css('overflow', '');

          proceedsearch();
        }
      });
    }

    // handle and trigger popup window;
    $('.popup-trigger').click(function(e) {
      e.stopPropagation();
      if (isfetched === false) {
        searchFunc(path, 'local-search-input', 'local-search-result');
      } else {
        proceedsearch();
      };
    });

    $('.popup-btn-close').click(onPopupClose);
    $('.popup').click(function(e){
      e.stopPropagation();
    });
    $(document).on('keyup', function (event) {
      var shouldDismissSearchPopup = event.which === 27 &&
        $('.search-popup').is(':visible');
      if (shouldDismissSearchPopup) {
        onPopupClose();
      }
    });
  </script>





  

  

  

  
  

  

  

  

</body>
</html>
